hdu4635Strongly connected

http://acm.hdu.edu.cn/showproblem.php?pid=4635

tarjan缩点统计缩点后每个结点的出度入度将那个包含原来点数最少的且出度或者入度为0的大节点看作一个整体内部连边n*（n-1)个连全部的；其它的点为一整体连全部的再两者连一同向的边保证它的出度或者入度依旧为0的情况下任意连最后减去原来的边M

  1 #include <iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<stdlib.h>
  5 #include<stack>
  6 using namespace std;
  7 #define N 100010
  8 #define M 100010
  9 #define INF 0xfffffff
 10 int a[110][110];
 11 stack<int>s;
 12 struct node
 13 {
 14     int u,v,next;
 15 }ed[M*2];
 16 int scc,sccno[N],head[N],lowlink[N],pre[N],dep,num[N],x[M],y[M],din[N],dout[N],o;
 17 void init()
 18 {
 19     o = 0;
 20     memset(head,-1,sizeof(head));
 21 }
 22 void add(int u,int v)
 23 {
 24     ed[o].u = u;
 25     ed[o].v = v;
 26     ed[o].next = head[u];
 27     head[u] = o++;
 28 }
 29 void dfs(int u)
 30 {
 31     int i;
 32     lowlink[u] = pre[u] = ++dep;
 33     s.push(u);
 34     for( i = head[u] ; i != -1 ; i = ed[i].next)
 35     {
 36         int v = ed[i].v;
 37         if(!pre[v])
 38         {
 39             dfs(v);
 40             lowlink[u] = min(lowlink[u],lowlink[v]);
 41         }
 42         else if(!sccno[v])
 43         lowlink[u] = min(lowlink[u],pre[v]);
 44     }
 45     if(lowlink[u]==pre[u])
 46     {
 47         scc++;
 48         for(;;)
 49         {
 50             int x = s.top();
 51             s.pop();
 52             sccno[x] = scc;
 53             if(x==u) break;
 54         }
 55     }
 56 }
 57 void find_scc(int n)
 58 {
 59     for(int i = 1; i <= n ;i++)
 60     if(!pre[i])
 61     dfs(i);
 62 }
 63 int main()
 64 {
 65     int i,t,n,m,a,b,kk=0;
 66     cin>>t;
 67     while(t--)
 68     {
 69         init();kk++;
 70         memset(num,0,sizeof(num));
 71         memset(pre,0,sizeof(pre));
 72         memset(din,0,sizeof(din));
 73         memset(dout,0,sizeof(dout));
 74         memset(sccno,0,sizeof(sccno));
 75         scanf("%d%d",&n,&m);
 76         for(i = 1; i <= m ; i++)
 77         {
 78             scanf("%d%d",&a,&b);
 79             x[i] = a;y[i] = b;
 80             add(a,b);
 81         }
 82         scc=0;dep=0;
 83         find_scc(n);
 84         printf("Case %d: ",kk);
 85         if(scc==1)
 86         {
 87             cout<<"-1
";
 88             continue;
 89         }
 90         for(i = 1; i <= n ; i++)
 91         num[sccno[i]]++;
 92         for(i = 1; i <= m ;i++)
 93         {
 94             if(sccno[x[i]]!=sccno[y[i]])
 95             {
 96                 dout[sccno[x[i]]]++;
 97                 din[sccno[y[i]]]++;
 98             }
 99         }
100         long long minz = INF;
101         for(i = 1 ;i <= scc ; i++)
102         if(minz>num[i]&&(din[i]==0||dout[i]==0))
103         minz = num[i];
104         long long ss=0;
105         ss = minz*(minz-1)+(n-minz)*(n-minz-1)+minz*(n-minz);
106         cout<<ss-m<<endl;
107     }
108     return 0;
109 }

View Code