先说一下题目的意思把。。 就是现在要求你去除掉图中的一个割点，判断去除哪一个割点能使得整个图分成的强联通分量最多，然后把这个强联通分量的数量输出就ok啦。。。
思路：从图中的强联通分量当中的点出发，然后如果该点作为根节点出发搜索的话，那么当他的强联通分量的孩子数量超过1的时候计数，然后当它不是根的时候，如果他的子节点访问时间戳比他大那么这个时候对于该割点也计数。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 #define min(a,b) a<b?a:b 4 #define N 10005 5 using namespace std; 6 struct node 7 { 8 int end,next; 9 }edge[(N*N-1)/2]; 10 int head[N],low[N],dfn[N],n,m,T,root,ff[N]; 11 void tarjan(int u) 12 { 13 dfn[u]=low[u]=++T; 14 int sons=0; 15 for(int i=head[u];i!=-1;i=edge[i].next) 16 { 17 if(!dfn[edge[i].end]) 18 { 19 tarjan(edge[i].end); 20 sons++; 21 low[u]=min(low[u],low[edge[i].end]); 22 if((u==root&&sons>1)||(u!=root&&dfn[u]<=low[edge[i].end]))ff[u]++;//最关键的，理解这两句就可以了。。。 23 } 24 else 25 low[u]=min(low[u],dfn[edge[i].end]); 26 } 27 } 28 int main() 29 { 30 int n,m,s,e; 31 while(scanf("%d%d",&n,&m)&&(n||m)) 32 { 33 if(m==0){printf("%d\n",n-1);continue;} 34 int i=0; 35 for(int i=0;i<n;i++)head[i]=-1,ff[i]=dfn[i]=low[i]=0; 36 while(m--) 37 { 38 scanf("%d%d",&s,&e); 39 edge[i].end=e; 40 edge[i].next=head[s]; 41 head[s]=i++; 42 edge[i].end=s; 43 edge[i].next=head[e]; 44 head[e]=i++; 45 } 46 int total=0,answer=0; 47 for(root=0;root<n;root++) 48 { 49 if(!dfn[root]) 50 { 51 tarjan(root); 52 total++; 53 } 54 if(ff[root]>answer)answer=ff[root]; 55 } 56 printf("%d\n",answer+total); 57 } 58 return 0; 59 } 60
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667111.html
