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