t个样例

n个点 m条边

求有手帕最多的人

A->B B->C 

C 2块 可以传递

先强联通一下 这里的权是强连通分量中有几个点

然后要建一下反图 入度为0的点就有可能是最大的点

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5   6 using namespace std;  7   8 #define MAXN 5010  9 #define MAXN1 30010 10  11 int head[MAXN],dfn[MAXN],low[MAXN],pa[MAXN],cou[MAXN],in[MAXN],ans[MAXN],s1[MAXN]; 12 bool vis[MAXN]; 13 int k,num,cnt; 14  15 struct edg 16 { 17     int next,to,fr; 18 }x[MAXN1]; 19  20 void add(int u,int v) 21 { 22     x[cnt].next=head[u]; 23     x[cnt].fr=u; 24     x[cnt].to=v; 25     head[u]=cnt++; 26 } 27 stack
         
          s; 28  29 void  dfs(int u) 30 { 31     dfn[u]=low[u]=k++; 32     vis[u]=1; 33     s.push(u); 34     int i; 35     for(i=head[u];i!=-1;i=x[i].next) 36     { 37         int t=x[i].to; 38         if(!dfn[t]) 39         { 40             dfs(t); 41             low[u]=min(low[u],low[t]); 42         } 43         else if(vis[t]) 44             low[u]=min(low[u],dfn[t]); 45     } 46     if(dfn[u]==low[u]) 47     { 48         num++; 49         while(!s.empty()) 50         { 51             int now=s.top(); 52             s.pop(); 53             pa[now]=num; 54             vis[now]=0; 55             cou[num]++; 56             if(now==u)break; 57         } 58     } 59 } 60 int sum; 61 void dfs1(int u) 62 { 63     vis[u]=1; 64     int i; 65     sum=sum+cou[u]; 66     for(i=head[u];i!=-1;i=x[i].next) 67     { 68         if(!vis[x[i].to]) 69             dfs1(x[i].to); 70     } 71 } 72 int main() 73 { 74     int t,ca; 75     scanf("%d",&t); 76     ca=1; 77  78     while(t--) 79     { 80         int n,m,i; 81         scanf("%d%d",&n,&m); 82         memset(head,-1,sizeof(head)); 83         cnt=0; 84         for(i=1;i<=m;i++) 85         { 86             int a,b; 87             scanf("%d%d",&a,&b); 88             add(a,b); 89         } 90         num=0; 91         k=1; 92         memset(dfn,0,sizeof(dfn)); 93         memset(low,0,sizeof(low)); 94         memset(vis,0,sizeof(vis)); 95         memset(pa ,0,sizeof(pa)); 96         memset(cou,0,sizeof(cou)); 97         memset(in, 0,sizeof(in)); 98         memset(ans,0,sizeof(ans)); 99 100         for(i=0;i
          
           m1)127 m1=sum;128 }129 }130 printf("Case %d: %d\n",ca++,m1-1);131 int c1=0;132 133 for(i=0;i