学步园

多校联赛4的一道题，，给一个有向图，问最多加多少条边后仍然不是强联通，以前总会遇到问最少加几条边让图成一个强连通图，比赛时自己就找到了答案，当时想着添加最多的边后一定是将原来的图连成两个强连通分量，而两个强连通分量间的边最多是两个联通分量的点数之积，再加上每个联通分量内部的点的边数就是所有的边数，再减去原来的边就是新加上的边了，把图强连通缩点后，求出每个出度或入度为0的联通分量为一个联通分量，剩余的所有联通分量连成一个联通分量形成的边数，取最大的。当时敲完代码提交wrong了，就怀疑自己的算法，自己又证明了一下，如果n个点，分为两个联通分量，一个点数为a，一个为b，边数就是a*(a-1)+b*(b-1)+a*b-m=n*n-a*b-n，所以要保证a*b尽量小，所以要选点数最小的入度或出度为0的联通分量为一个，剩余的点为一个联通分量，，，，最后发现自己的代码有问题，平常总习惯点坐标从0开始，所以写成了i<n，，，，，

#include<stdio.h>
#include<string.h>
#include<stack>
#define N 100010
using namespace std;
int belong[N],ins[N],low[N],dfs[N],idx,ans,head[N],num,n,m,in[N],out[N],cot[N];
struct edge
{
    int st,ed,next;
}E[N];
void addedge(int x,int y)
{
    E[num].st=x;
    E[num].ed=y;
    E[num].next=head[x];
    head[x]=num++;
}
stack<int>Q;
void Tarjan(int u)
{
    int i,v;
    dfs[u]=low[u]=idx++;
    ins[u]=1;
    Q.push(u);
    for(i=head[u];i!=-1;i=E[i].next)
    {
        v=E[i].ed;
        if(dfs[v]==-1)
        {
            Tarjan(v);
            low[u]=low[u]>low[v]?low[v]:low[u];
        }
        else if(ins[v]==1)
            low[u]=low[u]>dfs[v]?dfs[v]:low[u];
    }
    if(dfs[u]==low[u])
    {
        do
        {
            v=Q.top();
            Q.pop();
            ins[v]=0;
            belong[v]=ans;
            cot[ans]++;
        }while(v!=u);
        ans++;
    }
}
int main()
{
    int t,i,x,y,op=1,max;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        num=0;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
        }
        memset(dfs,-1,sizeof(dfs));
        memset(ins,0,sizeof(ins));
        memset(cot,0,sizeof(cot));
        idx=ans=0;
        for(i=1;i<=n;i++)
          if(dfs[i]==-1)
           Tarjan(i);
          printf("Case %d: ",op++); 
          if(ans==1)
          {printf("-1\n");continue;}
          memset(in,0,sizeof(in));
          memset(out,0,sizeof(out));
          for(i=0;i<num;i++)
          {
              x=belong[E[i].st];
              y=belong[E[i].ed];
              if(x==y)
              continue;
               out[x]++;
               in[y]++;
          }
          max=9999999;
          for(i=0;i<ans;i++)
          {
              if((in[i]==0||out[i]==0)&&max>cot[i])
                  max=cot[i];
          }
          printf("%d\n",n*n-max*(n-max)-n-m);
    }
    return 0;
}