hdu 4635 Strongly connected（强连通）

考强连通缩点，算模板题吧，比赛的时候又想多了，大概是不自信吧，才开始认真搞图论，把题目想复杂了。

题意就是给你任意图，保证是simple directed graph，问最多加多少条边能使图仍然是simple directed graph，即无重边且整个图非强连通。

容易想到把所有的点分成两个集合，只要在同一个方向上把所有边都连上就很理想。那么点该如何分配呢？差值尽可能的大，因为总的边数不单单是两集合之间的边，还要算上集合内部全部的边，注意集合内部是在保证不出现重边的条件下的所有的边。

令总点数为n，一个集合的点数为k，则两个集合内的边数分别为 k*(k-1)，(n-k)*(n-k-1)条，而两集合之间的边共有 k*(n-k)条，答案就是三个值相加再减去已有的m条边。

注意：虽然最理想的是一个集合里只有一个点，但实际是一个强连通的最小点集，见最后一组样例，而且可能都在一棵树上，所以只要缩点后找到出度或入度为0的分量中点数最小的就可以了。

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int MAXN=100100;
  7 
  8 struct Edge{
  9     int v,next;
 10     int vis;
 11     Edge(){}
 12     Edge(int _v,int _next):v(_v),next(_next),vis(0){}
 13  }edge[MAXN];
 14  
 15 int head[MAXN],tol;
 16 int stk[MAXN],dfn[MAXN],low[MAXN],top,TT;
 17 int sub[MAXN],scc,num[MAXN];
 18 
 19 int a[MAXN],b[MAXN];
 20 int in[MAXN],out[MAXN];
 21  
 22 void add(int u,int v)
 23 {
 24     edge[tol]=Edge(v,head[u]);
 25     head[u]=tol++;
 26 }
 27 
 28 void tarjan(int u)
 29 {
 30     int v;
 31     dfn[u]=low[u]=++TT;
 32     stk[top++]=u;
 33     for(int i=head[u];i!=-1;i=edge[i].next)
 34     {
 35         v=edge[i].v;
 36         if(edge[i].vis)
 37             continue;
 38         edge[i].vis=1;
 39         if(!dfn[v]){
 40             tarjan(v);
 41             low[u]=min(low[u],low[v]);
 42         }else if(!sub[v])
 43             low[u]=min(low[u],dfn[v]);
 44     }
 45     if(low[u]==dfn[u]){
 46         scc++;
 47         int s=0;
 48         do{
 49             v=stk[--top];
 50             sub[v]=scc;
 51             s++;
 52         }while(v!=u);
 53         num[scc]=s;
 54     }
 55 }
 56 
 57 void init()
 58 {
 59     tol=0;
 60     memset(head,-1,sizeof(head));
 61     
 62     memset(dfn,0,sizeof(dfn));
 63     memset(low,0,sizeof(low));
 64     memset(sub,0,sizeof(sub));
 65 }
 66 
 67 int main()
 68 {
 69     int T,n,m;
 70     scanf("%d",&T);
 71     for(int K=1;K<=T;K++)
 72     {
 73         scanf("%d%d",&n,&m);
 74         
 75         init();
 76         for(int i=0;i<m;i++)
 77         {
 78             scanf("%d%d",&a[i],&b[i]);
 79             add(a[i],b[i]);
 80         }
 81         
 82         TT=0;top=0;scc=0;
 83         for(int i=1;i<=n;i++)
 84             if(!dfn[i])
 85                 tarjan(i);
 86             
 87         if(scc==1){
 88             printf("Case %d: -1
",K);
 89             continue;
 90         }
 91 
 92         memset(in,0,sizeof(in));
 93         memset(out,0,sizeof(out));
 94         for(int i=0;i<m;i++)
 95         {
 96             if(sub[a[i]]!=sub[b[i]]){
 97                 out[sub[a[i]]]++;
 98                 in[sub[b[i]]]++;
 99             }
100         }
101         int min=1;
102         for(int i=1;i<=scc;i++)
103         {
104             if(!in[i]||!out[i])
105                 if(num[min]>num[i])
106                     min=i;
107         }
108         int k=num[min];
109         printf("Case %d: %d
",K,k*(k-1)+(n-k)*(n-k-1)+k*(n-k)-m);
110         
111     }
112     return 0;
113 }

View Code