也许你能写出一段精致的文字，但你却未必能写出一段精辟的代码。
这是我最近研究连通性问题的一个体验，有的人的书写了好几页纸，可是最终能用的却只有1，2句话而已，我觉得在计算机的世界，没有什么比代码更能直接地表达出这个算法的本质了！所以我以后要多读代码，少看那些空洞的文字。
言归正传，来看题，这是我写的第一个强连通分量的题目，其实求强连通分量的步骤非常简单，正反两次使用dfs，就能得到联通分量的一切信息。做完题目我发现，其实求联通分量最大的作用倒在于，联通分量可以缩成一点，考虑为一个整体，这样可以简化构图，发掘出各个强连通分量外部之间的规律。
解题的方法就是：找出图中所有的强连通分量并将他们缩成一点，再用外部的边重新建图，统计出新图中出度为0的点，如果只有一个，那么说明这个强连通分量中的所有点就是题目要求的点。
题目中要特别注意：内存池中预开的点必须是边的三倍大小，因为构建正图，反图和新图都需要新建节点。（因为这个我wa了一次）
还有就是绝对不要使用vector,我用vector写了一个程序，跑了600+MS,用链表.....47MS......10倍以上的差距，汗 - -！
#include<iostream>
using namespace std;
#define DOTMAX 10001
#define EDGEMAX 50001
struct node
{
int t;
node *next;
}dotset[EDGEMAX*3];
int count=0;//每一个case后,count置为0
node *Newnode()
{
node *p;
p=&dotset[count];
count++;
return p;
}
void Addnode(node hash[],int a,int b)
{
node *p=&hash[a];
node *q=Newnode();
q->t=b;
q->next=p->next;
p->next=q;
}
node hash[DOTMAX];
node nhash[DOTMAX];
node New[DOTMAX];
int gcc;
int order[DOTMAX];
int num;
int id[DOTMAX];
int visit[DOTMAX];
int gccnum[DOTMAX];
void init(node hash[],int n)
{
count=0;
int i;
for(i=1;i<=n;i++)
{
hash[i].t=-1;
hash[i].next=NULL;
}
}
int n,m;
void dfs(int u)
{
visit[u]=1;
node *p;
int v;
for(p=hash[u].next;p!=NULL;p=p->next)
{
v=p->t;
if(!visit[v])
{
dfs(v);
}
}
num++;
order[num]=u;
}
void ndfs(int u)
{
visit[u]=1;
id[u]=gcc;
node *p;
int v;
for(p=nhash[u].next;p!=NULL;p=p->next)
{
v=p->t;
if(!visit[v])
{
ndfs(v);
}
}
}
int main()
{
int a,b,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(hash,n);
init(nhash,n);
init(New,n);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
Addnode(hash,a,b);
Addnode(nhash,b,a);
}
memset(visit,0,sizeof(visit));
num=0;
for(i=1;i<=n;i++)
{
if(!visit[i])
dfs(i);
}
memset(visit,0,sizeof(visit));
gcc=0;
for(i=num;i>=1;i--)
{
if(!visit[order[i]])
{
gcc++;
ndfs(order[i]);
}
}
for(i=1;i<=n;i++)
{
node *p;
for(p=hash[i].next;p!=NULL;p=p->next)
{
if(id[i]!=id[p->t])
{
Addnode(New,id[i],id[p->t]);
}
}
}
int cnt=0;
memset(gccnum,0,sizeof(gccnum));
for(i=1;i<=n;i++)
{
gccnum[id[i]]++;
}
int mark=0;
for(i=1;i<=gcc;i++)
{
if(New[i].next==NULL)
{
cnt++;
mark=i;
}
}
if(cnt==1)
{
printf("%d\n",gccnum[mark]);
}
else
printf("%d\n",0);
}
return 0;
}