http://poj.org/problem?id=2186
经典强连通分支，求解步骤是用tarjan算法求出强连通分支，然后缩点构成DAG，查看DAG中出度为0的点，若个数不等于1则不存在答案，输出0
还可以使用tarjan算法的改进版gabow算法，后者在求解强连通分量的根时采用了更简单的方式
tarjan代码
View Code
1 #include <stdio.h>
2 #include <memory.h>
3 #define e 50001
4 #define v 10001
5 #define MIN(a,b) ((a)<(b)?(a):(b))
6 struct node
7 {
8 int end;
9 node*next;
10 void fun()
11 {
12 end=0;
13 next=NULL;
14 }
15 }edge[e],*head[e],*tmp;
16 int dfn[v],low[v],stack[v],father[v],counter[v];
17 bool instack[v],out[v];
18 int n,m,a,b,sum,num,T;
19 void add(int a,int b) //此处采用了邻接表的形式减少内存消耗，这种构图形式值得学习
20 {
21 tmp->end=b;
22 tmp->next=head[a];
23 head[a]=tmp++;
24 }
25 void tarjan(int root) //接下来就是简单的tarjan算法，不懂得话可以上百度
26 {
27 int k;
28 dfn[root]=low[root]=++T;
29 instack[root]=true;
30 stack[++num]=root;
31 for(node *p=head[root];p;p=p->next)
32 {
33 k=p->end;
34 if(!low[k])
35 {
36 tarjan(k);
37 low[root]=MIN(low[root],low[k]);
38 }
39 else if(instack[root])
40 low[root]=MIN(low[root],low[k]);
41 }
42 if(dfn[root]==low[root])
43 {
44 sum++;
45 for(;stack[num+1]!=root;num--)
46 {
47 instack[stack[num]]=false;
48 father[stack[num]]=sum;
49 }
50 }
51 }
52 int main()
53 {
54 scanf("%d %d",&n,&m);
55 memset(head,NULL,sizeof(head));
56 for(int i=0;i<=m;i++)
57 edge[i].fun();
58 memset(low,0,sizeof(low));
59 memset(instack,false,sizeof(instack));
60 memset(out,true,sizeof(out));
61 memset(counter,0,sizeof(counter));
62 tmp=edge;
63 for(int i=0;i<m;i++)
64 {
65 scanf("%d %d",&a,&b);
66 add(a,b);
67 }
68 T=num=sum=0;
69 for(int i=1;i<=n;i++)
70 if(!low[i])
71 tarjan(i);
72 for(int i=1;i<=n;i++) //此处是统计出度为0的点和个连通分支内点的个数
73 {
74 counter[father[i]]++;
75 for(node *p=head[i];p;p=p->next)
76 if(father[i]!=father[p->end])
77 out[father[i]]=false;
78 }
79 int number=0,answer;
80 for(int i=1;i<=sum;i++)
81 {
82 if(out[i])
83 {
84 number++;
85 answer=counter[i];
86 }
87 }
88 if(number==1)
89 printf("%d\n",answer);
90 else
91 printf("0\n");
92 return 0;
93 }
gabow代码
View Code
1 #include <stdio.h>
2 #include <memory.h>
3 #define E 50001
4 #define V 10001
5 struct node
6 {
7 int num;
8 node*next;
9 void fun()
10 {
11 num=0;
12 next=NULL;
13 }
14 }E_table[E],*head[V],*E_tmp,Scc_table[E],*Scc_head[V],*Scc_tmp;
15 int n,m,root_stack[V],scc[V],father[V],init[V],timer,scc_num,counter[V];
16 void add(int a,int b)
17 {
18 E_tmp->num=b;
19 E_tmp->next=head[a];
20 head[a]=E_tmp++;
21 }
22 void scc_add(int a,int b)
23 {
24 Scc_tmp->num=b;
25 Scc_tmp->next=Scc_head[a];
26 Scc_head[a]=Scc_tmp++;
27 }
28 void Gabow(int key)
29 {
30 root_stack[++root_stack[0]]=scc[++scc[0]]=key;
31 init[key]=++timer;
32 for(node*tmp=head[key];tmp;tmp=tmp->next)
33 {
34 if(!init[tmp->num])
35 Gabow(tmp->num);
36 else if(!father[tmp->num])
37 while(init[root_stack[root_stack[0]]]>init[tmp->num])
38 root_stack[0]--;
39 }
40 if(key==root_stack[root_stack[0]])
41 {
42 scc_num++,root_stack[0]--;
43 do
44 father[scc[scc[0]]]=scc_num;
45 while(scc[scc[0]--]!=key);
46 }
47 }
48 void ini()
49 {
50 memset(head,NULL,sizeof(head));
51 memset(Scc_head,NULL,sizeof(Scc_head));
52 memset(counter,0,sizeof(counter));
53 memset(init,0,sizeof(init));
54 memset(father,0,sizeof(father));
55 }
56 int main()
57 {
58 while(scanf("%d %d",&n,&m)==2)
59 {
60 E_tmp=E_table;
61 for(int i=0,a,b;i<m;i++)
62 {
63 scanf("%d %d",&a,&b);
64 add(a,b);
65 }
66 scc_num=timer=0;
67 for(int i=1;i<=n;i++)
68 if(!init[i])
69 Gabow(i);
70 Scc_tmp=Scc_table;
71 for(int i=1;i<=n;i++)
72 {
73 counter[father[i]]++;
74 for(node*tmp=head[i];tmp;tmp=tmp->next)
75 if(father[i]!=father[tmp->num])
76 scc_add(father[i],father[tmp->num]);
77 }
78 int number=0,num;
79 for(int i=1;i<=scc_num;i++)
80 if(!Scc_head[i])
81 number++,num=counter[i];
82 if(number==1)
83 printf("%d\n",num);
84 else
85 printf("0\n");
86 ini();
87 }
88 return 0;
89 }