判断强连通图之后，果断要做做强连通分量的题目，之前做求割点的题目的时候就已经学过了tarjan算法了。。 但是还是不会用，一开始看到这个题目的时候不知道怎么办，感觉就是有种怪怪的感觉。。 看了网上的代码，出度和入度的判断真的还蛮精妙的。。
通过一边tarjan算法已经将一个图分解成了很多个前连通图了。。。 这要计算出每一个前连通分量的入度和出度来，然后添加的边只要能使所有强连通分量连通就可以。。所以只用添加max(入度缺少,出度缺少)。。
View Code 1 #include<iostream> 2 #define min(a,b) a<b?a:b 3 #define max(a,b) a>b?a:b 4 using namespace std; 5 struct node 6 { 7 int e,next; 8 }edge[50002]; 9 int head[20002],exist[20002],dfn[20002],low[20002],stack[20002],weight[20002],n,m,s,e,top,Count,Time; 10 int ind[20002],outd[20002]; 11 void tarjan(int u) 12 { 13 stack[top++]=u; 14 dfn[u]=low[u]=++Time; 15 exist[u]=1; 16 for(int end=head[u];end!=-1;end=edge[end].next) 17 { 18 if(!dfn[edge[end].e]) 19 { 20 tarjan(edge[end].e); 21 low[u]=min(low[u],low[edge[end].e]); 22 } 23 else 24 { 25 if(exist[edge[end].e]==1) 26 low[u]=min(low[u],dfn[edge[end].e]); 27 } 28 } 29 if(dfn[u]==low[u]) 30 { 31 while(u!=stack[top]) 32 { 33 weight[stack[top-1]]=Count; 34 exist[stack[top-1]]=0; 35 top--; 36 } 37 Count++; 38 } 39 } 40 int main() 41 { 42 int t; 43 scanf("%d",&t); 44 while(t--) 45 { 46 scanf("%d%d",&n,&m); 47 for(int i=0;i<=n;i++) 48 { 49 head[i]=-1; 50 ind[i]=outd[i]=exist[i]=weight[i]=low[i]=dfn[i]=0; 51 } 52 Time=top=Count=0; 53 for(int i=0;i<m;i++) 54 { 55 scanf("%d%d",&s,&e); 56 edge[i].e=e; 57 edge[i].next=head[s]; 58 head[s]=i; 59 } 60 for(int i=1;i<=n;i++) 61 { 62 if(!dfn[i]) 63 { 64 tarjan(i); 65 } 66 } 67 if(Count==1){printf("0\n");continue;} 68 else 69 { 70 for(int i=1;i<=n;i++) 71 { 72 for(int end=head[i];end!=-1;end=edge[end].next) 73 { 74 if(weight[i]!=weight[edge[end].e]) 75 { 76 ind[weight[edge[end].e]]++; 77 outd[weight[i]]++; 78 } 79 } 80 } 81 int maxin=0,maxout=0; 82 for(int i=0;i<Count;i++) 83 { 84 if(ind[i]==0)maxout++; 85 if(outd[i]==0)maxin++; 86 } 87 printf("%d\n",max(maxout,maxin)); 88 } 89 } 90 return 0; 91 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667108.html
