https://vjudge.net/problem/HDU-4635#author=634579757
有t组数据，给了一个n个点m条边的有向图，问给此图最多加多少条边，满足如下条件:
1：此图不能强连通
2：没有重边和自环
3：当图本身就是强连通的时候就输出-1
那么现在我们考虑，如何加边使得加的边尽可能的多，又不强连通.　在使图不强连通的前提下，要添加尽可能多的边。边至多有n∗(n−1)条，而已经给了m条，那么所能添加的边数不可能超过k=n∗(n−1)−m。
　　这k条边还有部分不能添加，一添加立刻就强连通。一个强连通图最少只需要n条边，根据强连通的特性，缩点之后必定是不会有环的存在的，那么只要继续保持没有环的存在即可。我们只要让其中1个强连通分量没有出度，或者没有入度就行了。到底选哪个强连通分量？选点数少的，这点在后面会了解。
例如1×10=10，2×9=18，故选点数越小的SCC越好
　　如果挑出1个出度（入度也行的，同理）为0的强连通分量，该强连通分量的点数为d，那么答案就是k-d(n-d)，即不允许有其他n-d个点有任何一条边指向此强连通分量，其他边都是可以存在的。那么要使得k-d(n-d)最大，那么d(n-d)要最小，就是上面讲的要选哪个强连通分量的原因。
　　那么应该找到缩点后出/入度为0的且包含点数最少的强连通分量来计算即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
int ver[N],Next[N],head[N],dfn[N],low[N];
int stack[N],ins[N],in[N],out[N],scc_cnt[N],c[N];
int n,m,tot,num,top,cnt,t,count=1,minv;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    stack[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=Next[i])
        if(!dfn[ver[i]]){
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if(ins[ver[i]])
            low[x]=min(low[x],dfn[ver[i]]);
    if(dfn[x]==low[x]){
        cnt++;int y;
        do{
            y=stack[top--],ins[y]=0;
            c[y]=cnt,scc_cnt[cnt]++;
        }while(x!=y);
    }
}
void init(){
    minv=1e9;cnt=0;top=0;tot=0;
    memset(head,0,sizeof head);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(scc_cnt,0,sizeof scc_cnt);
    memset(in,0,sizeof in);
    memset(out,0,sizeof out);
    memset(c,0,sizeof c);
}
int main(){
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])    tarjan(i);
        for(int x=1;x<=n;x++)
            for(int i=head[x];i;i=Next[i]){
                int y=ver[i];
                if(c[x]==c[y])    continue;
                in[c[y]]++,out[c[x]]++;
            }
        for(int i=1;i<=cnt;i++)
            if(!in[i]||!out[i])    minv=min(minv,scc_cnt[i]);
        if(cnt==1)    printf("Case %d: -1\n",count++);
        else printf("Case %d: %lld\n",count++,(ll)n*(n-1)-(ll)m-(ll)minv*(n-minv));
    }
    return 0;
}