题意：
给一个n个点的简单有向图，问最多能加多少条边使得该图仍然是简单有向图，且不是强连通图。简单有向图的定义为：没有重边，无自环。 强连通图的定义为：整个图缩点后就只有一个点，里面包含n个原点，也就是一个连通分量。如果一开始就是一个强连通图，则输出-1。
思路：
要加边最多那么加边后的图连通分量越少越好，那么连通分量最少也就是2个。先用n个点构造一个完全图（有向图有：n*(n-1)条边，无向图有：n*(n-1)/2条边），再用构造的边 减去原来有的m条边=ans。再用强连通算法缩点，记录每个新点包含点的个数，从入度为0或出度为0的新点中找出包含点数最小的minnum，再用上面剩余的边ans - minnum*(n-minnum)就是所要的答案。因为如果不减入度为0或出度为0相关的边，那么该点本身包含有入边和出边，加的边永远都是强连通图。所以只能去掉与入度为0或出度为0点的相关边，只减掉一个方向的边，要么全是（n-minnum）点数到minnum点数的入边，那么是minnum点数到(n-minnum)点数的出边。
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int N = ;
struct EDG{
int to,next;
}edg[N]; int eid,head[N],low[N],dfn[N],vist[N],num[N],id[N],deep,stack1[N],tn,top,in[N],out[N]; void init()
{
eid=tn=top=deep=;
memset(head,-,sizeof(head));
memset(vist,,sizeof(vist));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(num,,sizeof(num));
} void addEdg(int u,int v)
{
edg[eid].to=v; edg[eid].next=head[u]; head[u]=eid++;
} void Tarjan(int u)
{
stack1[++top]=u;
vist[u]=;
deep++;
low[u]=dfn[u]=deep;
for(int i=head[u]; i!=-; i=edg[i].next)
{
int v=edg[i].to;
if(vist[v]==)
{
vist[v]=;
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vist[v]==)
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
tn++;
do{
vist[stack1[top]]=;
num[tn]++;
id[stack1[top]]=tn;
}while(stack1[top--]!=u); }
} long long solve(int n,int m)
{
long long ans=n*(n-)-m;
int minnum=N;
for(int i=; i<=n; i++)
if(vist[i]==)
Tarjan(i);
if(tn==) return -;
for(int u=; u<=n; u++)
for(int i=head[u]; i!=-; i=edg[i].next)
{
int v=edg[i].to;
if(id[u]!=id[v])
in[id[v]]++,out[id[u]]++;
}
for(int i=; i<=tn; i++)
if(in[i]==||out[i]==)
{
minnum=min(minnum,num[i]);
}
ans-=minnum*(n-minnum);
return ans;
} int main()
{
int t,n,m,c=,a,b;
cin>>t;
while(t--)
{
cin>>n>>m;
init();
for(int i=; i<=m; i++)
{
cin>>a>>b;
addEdg(a,b);
}
printf("Case %d: %I64d\n",++c,solve(n,m));
}
}