强连通图（最多加入几条边使得图仍为非强连通图）G

题目链接：https://cn.vjudge.net/contest/67418#problem/G

具体思路：首先用tarjan缩点，这个时候就会有很多个缩点，然后再选取一个含有点数最少，并且当前这个点的出度和入度至少有一个为0，这个原因后面解释。然后选出最少的点 t1 后，当前的图就可以看成两个“缩点”了，除了选出来的t1点，其他点可以形成一个联通块，然后这两个缩点之间可以连着单向边，这样的话能加的边数是最多的。关于为什么选取最小的出度或者入度为0的缩点，就在于两个联通块相连的时候，只能连单向边，如果当前选取的缩点联通块出度和入度都不是0，那么就不会满足单向边的情况了。

minn是满足情况的最小的点。

所以，最多加的边数就是（minn）×（minn-1）+（n-minn）×（n-minn-1）+（minn）×（m-minn）-m。

AC代码：

  1 #include<iostream>
  2 #include<string>
  3 #include<iomanip>
  4 #include<stack>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cmath>
  8 #include<cstring>
  9 #include<stdio.h>
 10 #include<map>
 11 using namespace std;
 12 # define ll long long
 13 # define inf 0x3f3f3f3f
 14 const int maxn = 1000000+100;
 15 int head[maxn],low[maxn],dfn[maxn],istack[maxn];
 16 int in[maxn],out[maxn];
 17 ll col,num,ind;
 18 stack<int>q;
 19 map<ll,ll>color;
 20 struct node
 21 {
 22     int fr;
 23     int to;
 24     int nex;
 25 } edge[maxn*3];
 26 void addedge(int fr,int to)
 27 {
 28     edge[num].fr=fr;
 29     edge[num].to=to;
 30     edge[num].nex=head[fr];
 31     head[fr]=num++;
 32 }
 33 void init()
 34 {
 35     ind=0,num=0,col=0;
 36     color.clear();
 37     while(!q.empty())q.pop();
 38     memset(in,0,sizeof(in));
 39     memset(out,0,sizeof(out));
 40     memset(low,0,sizeof(low));
 41     memset(dfn,0,sizeof(dfn));
 42     memset(istack,0,sizeof(istack));
 43     memset(head,-1,sizeof(head));
 44 }
 45 void tarjan(int u,int root)
 46 {
 47     low[u]=dfn[u]=++ind;
 48     q.push(u);
 49     for(int i=head[u]; i!=-1; i=edge[i].nex)
 50     {
 51         int v=edge[i].to;
 52         if(dfn[v]==0)
 53         {
 54             tarjan(v,u);
 55             low[u]=min(low[u],low[v]);
 56         }
 57         else if(istack[v]==0)
 58         {
 59             low[u]=min(low[u],dfn[v]);
 60         }
 61     }
 62     if(low[u]==dfn[u])
 63     {
 64         int t;
 65         col++;
 66         do
 67         {
 68             t=q.top();
 69             q.pop();
 70             //   cout<<t<<endl;
 71             istack[t]=col;
 72             color[col]++;
 73         }
 74         while(t!=u);
 75     }
 76 }
 77 int main()
 78 {
 79     int T;
 80     scanf("%d",&T);
 81     int Case=0;
 82     while(T--)
 83     {
 84         init();
 85         ll n,m;
 86         scanf("%lld %lld",&n,&m);
 87         int t1,t2;
 88         for(int i=1; i<=m; i++)
 89         {
 90             scanf("%d%d",&t1,&t2);
 91             addedge(t1,t2);
 92         }
 93         for(int i=1; i<=n; i++)
 94         {
 95             if(dfn[i]==0)
 96                 tarjan(i,1);
 97         }
 98         for(int i=0; i<num; i++)
 99         {
100             t1=edge[i].fr,t2=edge[i].to;
101             if(istack[t1]!=istack[t2])
102             {
103                 in[istack[t2]]++;
104                 out[istack[t1]]++;
105             }
106         }
107         ll minn=inf;
108         for(int i=1; i<=col; i++)
109         {
110             if(in[i]==0||out[i]==0)
111             {
112                 minn=min(minn,color[i]);
113             }
114         }
115         printf("Case %d: ",++Case);
116         if(col==1)
117         {
118             printf("-1
");
119             continue;
120         }
121         printf("%lld
",minn*(minn-1)+(n-minn)*(n-minn-1)+(minn)*(n-minn)-m);
122     }
123     return 0;
124 }
125