昨天开始了强连通，原本以为这一道题目是求强连通分量的个数的。。。但是题意就是求这是否是一个强连通图。。
所以题意不解释了。。
做题方法大概就是，先深搜一边，入栈，从栈顶去元素深搜如果能够搜到所有的点，那么就说明这是一个强连通图。
举个例子，如果图能从节点1出发寻找到所有的点，然后现在将有向边方向，如果还能搜到所有的点的话，就是一个强连通图，因为能够通过1搜索所有点，然后反边就说明能够从任一点到达1点。。
理解了上面这段话就好说了。。
View Code 1 #include<iostream> 2 using namespace std; 3 #define Size 100010 4 struct node 5 { 6 int e,next; 7 }edge1[Size],edge2[Size]; 8 int stack[10002],head1[10002],head2[10003],top,visit[10002]; 9 void dfs(int i) 10 { 11 visit[i]=1; 12 for(int end=head1[i];end!=-1;end=edge1[end].next) 13 { 14 if(!visit[edge1[end].e]) 15 { 16 dfs(edge1[end].e); 17 } 18 } 19 stack[top++]=i; 20 } 21 void dfs1(int i) 22 { 23 visit[i]=1; 24 for(int end=head2[i];end!=-1;end=edge2[end].next) 25 { 26 if(!visit[edge2[end].e]) 27 { 28 dfs1(edge2[end].e); 29 } 30 } 31 } 32 int main() 33 { 34 int m,n,s,e,flag; 35 while(scanf("%d%d",&n,&m)&&(m!=0||n!=0)) 36 { 37 memset(head1,-1,sizeof(head1)); 38 memset(head2,-1,sizeof(head2)); 39 memset(visit,0,sizeof(visit)); 40 for(int i=0;i<m;i++) 41 { 42 scanf("%d%d",&s,&e); 43 edge1[i].e=e; 44 edge1[i].next=head1[s]; 45 head1[s]=i; 46 edge2[i].e=s; 47 edge2[i].next=head2[e]; 48 head2[e]=i; 49 } 50 flag=top=0; 51 for(int i=1;i<=n;i++) 52 { 53 if(!visit[i]) 54 { 55 flag++; 56 dfs(i); 57 } 58 } 59 memset(visit,0,sizeof(visit)); 60 for(int i=top-1;i>=0;i--) 61 { 62 if(flag>1)break; 63 if(!visit[stack[i]]) 64 { 65 flag++; 66 dfs1(stack[i]); 67 } 68 } 69 if(flag==1)printf("Yes\n"); 70 else 71 printf("No\n"); 72 } 73 return 0; 74 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667104.html
