题目链接：https://vjudge.net/problem/HDU-4635
题目：有向图，给定若干个连通图，求最多还能添加几条边，添完边后，图仍然要满足
（1）是简单图，即没有重边或者自环
（2）不是有向强连通图
思路：我们可以这么想，n个顶点，一个有向图边数最多，就是有向完全图，则边数为n*(n-1)。
要满足不是强连通图，我们可以假设有一个tarjan缩成的点（scc），它不能到达其他所有点，或者其他所有点
不能到达它，假设这个scc有k个顶点，也就是说，k*(n-k)条边是不存在的，那么最大添加边数应该是 n*(n-1) - k*(n-k) - m(本来有的边) ---- ①
给定的图情况不确定，我们先进行tarjan缩点，分成若干个scc，每个scc中也记录各自scc中的顶点数，然后进行scc的入度出度统计。
为使添加的边能最多，我们选所有的入度为0或者出度为0的scc 套入 公式①，选最大即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = (int)1e5+;
int n,m,tot,tim,scc,top;
int head[N],dfn[N],low[N],scc_no[N],s[N],ins[N];
struct node{
int to;
int nxt;
}e[N];
struct col{
int ru;
int chu;
int cnt;
}col[N];//强连通分量 void init(){
for(int i = ; i <= n; ++i){
head[i] = -;
col[i].ru = col[i].chu = dfn[i] = ;
}
tot = tim = scc = ;
} inline void add(int u,int v){
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot++;
} void tarjan(int now,int pre){
dfn[now] = low[now] = ++tim;
ins[now] = ; s[top++] = now;
int to;
for(int o = head[now]; ~o; o = e[o].nxt){
to = e[o].to;
// if(to == pre) continue;
if(!dfn[to]){
tarjan(to,now);
low[now] = min(low[now],low[to]);
}
else if(ins[to]) low[now] = min(low[now],dfn[to]);
} if(dfn[now] == low[now]){
int x,cnt = ;
++scc;
do{
x = s[--top];
ins[x] = ;
scc_no[x] = scc;
++cnt;
}while(now != x);
col[scc].cnt = cnt;//每个强连通分量包含几个点
}
} //入度出度统计
void du_cnt(){
int to;
for(int now = ; now <= n; ++now){
for(int o = head[now]; ~o; o = e[o].nxt){
to = e[o].to;
if(scc_no[to] == scc_no[now]) continue;
++col[scc_no[to]].ru;
++col[scc_no[now]].chu;
}
}
} void solve(int _case){
for(int i = ; i <= n; ++i)
if(!dfn[i]) tarjan(i,i); ll ans = (ll)n*(n-) - m;
ll useless = (1LL) << ;
du_cnt();
for(int i = ; i <= scc; ++i){
if(!col[i].ru || !col[i].chu){
useless = min(useless,(ll)col[i].cnt*(n-col[i].cnt));
}
}
if(scc == ) printf("Case %d: -1\n",_case);
else printf("Case %d: %lld\n",_case,ans-useless);
} int main(){ int T,u,v;
scanf("%d",&T);
for(int i = ; i <= T; ++i){
scanf("%d%d",&n,&m);
init();
for(int x = ; x <= m; ++x){
scanf("%d%d",&u,&v);
add(u,v);
}
solve(i);
} return ;
}