题意很明显，就是说现在有n个孩子正在玩游戏，完成一个传递的游戏，举个例子，A传递到B小朋友，然后B小朋友传递给C小朋友，那么此时，C小朋友将拥有2的传递值，C是胜利者，若C又传递回A，那么A,B,C三者都拥有传递值为2的胜利者，说白了就是强连通的一个练习。
思路就是分清楚这整个图当中的强连通分量，每个分量包含了哪些点，将这些分量缩成一个点，然后建立这些点的一个反向图，然后每次从入度为0的强连通分量深搜，最后标记哪些强连通分量为max。那么只要该点所属的强连通分量为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 s,e,next; 8 }edge1[500002],edge2[500002]; 9 int head1[5002],head2[5002],dfn[5002],low[5002],stack[5002],exsit[5002],weight[5002],color[5002],n,m,s,e,top,Count,Time; 10 int ind[5002],Max,sum; 11 void tarjan(int u) 12 { 13 dfn[u]=low[u]=++Time; 14 stack[top++]=u; 15 exsit[u]=1; 16 for(int end=head1[u];end!=-1;end=edge1[end].next) 17 { 18 if(!dfn[edge1[end].e]) 19 { 20 tarjan(edge1[end].e); 21 low[u]=min(low[u],low[edge1[end].e]); 22 } 23 else 24 if(exsit[edge1[end].e]==1) 25 low[u]=min(low[u],dfn[edge1[end].e]); 26 } 27 if(dfn[u]==low[u]) 28 { 29 Count++; 30 int v; 31 do 32 { 33 v=stack[top-1]; 34 exsit[v]=0; 35 weight[v]=Count; 36 color[Count]++; 37 top--; 38 }while(u!=v); 39 40 } 41 } 42 void dfs(int i) 43 { 44 sum+=color[i]; 45 exsit[i]=1; 46 Max=max(Max,sum); 47 for(int j=head2[i];j!=-1;j=edge2[j].next) 48 { 49 if(exsit[edge2[j].e]==0) 50 { 51 dfs(edge2[j].e); 52 } 53 } 54 return ; 55 } 56 int main() 57 { 58 int t,T=0; 59 scanf("%d",&t); 60 while(t--) 61 { 62 scanf("%d%d",&n,&m); 63 for(int i=0;i<=n;i++) 64 { 65 head1[i]=head2[i]=-1; 66 color[i]=weight[i]=exsit[i]=dfn[i]=low[i]=0; 67 } 68 for(int i=0;i<m;i++) 69 { 70 scanf("%d%d",&s,&e); 71 edge1[i].s=s; 72 edge1[i].e=e; 73 edge1[i].next=head1[s]; 74 head1[s]=i; 75 } 76 Time=top=Count=0; 77 for(int i=0;i<n;i++) 78 { 79 if(!dfn[i]) 80 { 81 tarjan(i); 82 } 83 } 84 for(int i=1;i<=Count;i++) 85 { 86 dfn[i]=ind[i]=0; 87 } 88 Time=0; 89 for(int i=0;i<m;i++) 90 { 91 int start=weight[edge1[i].s]; 92 int end=weight[edge1[i].e]; 93 if(start!=end) 94 { 95 edge2[Time].e=start; 96 edge2[Time].next=head2[end]; 97 head2[end]=Time++; 98 ind[start]++; 99 } 100 } 101 int maxsize=0; 102 for(int i=1;i<=Count;i++) 103 { 104 105 if(ind[i]==0) 106 { 107 for(int j=1;j<=Count;j++)exsit[j]=0; 108 Max=sum=0; 109 dfs(i); 110 dfn[i]=Max; 111 maxsize=max(dfn[i],maxsize); 112 } 113 } 114 int flag=0; 115 printf("Case %d: %d\n",++T,maxsize-1); 116 for(int i=0;i<n;i++) 117 { 118 if(dfn[weight[i]]==maxsize) 119 { 120 if(!flag){printf("%d",i);flag=1;} 121 else 122 printf(" %d",i); 123 } 124 } 125 printf("\n"); 126 } 127 return 0; 128 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667106.html
