也許你能寫出一段精致的文字，但你卻未必能寫出一段精辟的代碼。
這是我最近研究連通性問題的一個體驗，有的人的書寫了好幾頁紙，可是最終能用的卻只有1，2句話而已，我覺得在計算機的世界，沒有什么比代碼更能直接地表達出這個算法的本質(zhì)了！所以我以后要多讀代碼，少看那些空洞的文字。
言歸正傳，來看題，這是我寫的第一個強連通分量的題目，其實求強連通分量的步驟非常簡單，正反兩次使用dfs，就能得到聯(lián)通分量的一切信息。做完題目我發(fā)現(xiàn)，其實求聯(lián)通分量最大的作用倒在于，聯(lián)通分量可以縮成一點，考慮為一個整體，這樣可以簡化構(gòu)圖，發(fā)掘出各個強連通分量外部之間的規(guī)律。
解題的方法就是：找出圖中所有的強連通分量并將他們縮成一點，再用外部的邊重新建圖，統(tǒng)計出新圖中出度為0的點，如果只有一個，那么說明這個強連通分量中的所有點就是題目要求的點。
題目中要特別注意：內(nèi)存池中預(yù)開的點必須是邊的三倍大小，因為構(gòu)建正圖，反圖和新圖都需要新建節(jié)點。（因為這個我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;
}