题意：先给你一个n个点，m条边的有向图，问你最多能够增加多少条边，使得这个图不是一个强连通图
解题思路：考虑最多要添加的边数，所以如果能把初始图划分成两个部分，每个部分都是完全图，这两个部分分别用单向边连接，这样一定是最优的，所以，首先先缩点，因为一个强连通子图的所有点一定要在同一个部分中，缩完点后考虑只有入度和出度为0的点成一个部分才能有最优解，跑所有满足情况的点，当某个点的入度或者出度为0的时候，因为边数最多为两个部分的完全子图+两个部分点的乘积(单向边)-m条给出的边
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=2e5;
struct Edge
{
ll to;
ll next;
}edge[maxn];
ll low[maxn],dfn[maxn],instack[maxn],sccno[maxn],visit[maxn],head[maxn];
ll scc_cnt,n,m,step,index,cnt;
ll x[maxn],y[maxn];
ll indeg[maxn],outdeg[maxn];
vector<ll>scc[maxn];
bool cnp(int x,int y)
{
return y>x;
}
void add(ll u,ll v)
{
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt++;
}
void tarjan(ll u)
{
low[u]=dfn[u]=++step;
instack[++index]=u;
visit[u]=;
for(ll i=head[u];i!=-;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[u]=min(low[u],low[edge[i].to]);/*更新儿子节点；*/
}
else if(visit[edge[i].to])
{
low[u]=min(low[u],dfn[edge[i].to]);/*更新回边；*/
}
}
if(low[u]==dfn[u])
{
scc_cnt++;
scc[scc_cnt].clear();
do
{
scc[scc_cnt].push_back(instack[index]);
sccno[instack[index]]=scc_cnt;
visit[instack[index]]=;
index--;
}
while(u!=instack[index+]);
}
return;
}
void init()
{
memset(indeg,,sizeof(indeg));
memset(outdeg,,sizeof(outdeg));
memset(head,-,sizeof(head));
cnt=step=index=scc_cnt=;
memset(visit,,sizeof(visit));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
for(int i=;i<=n;i++)
scc[i].clear();
}
int main()
{
ll t;
ll cot=;
scanf("%lld",&t);
while(t--)
{
cot++;
scanf("%lld%lld",&n,&m);init();
for(int i=;i<=m;i++)
{
scanf("%lld%lld",&x[i],&y[i]);
add(x[i],y[i]);
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
printf("Case %d: ",cot);
if(scc_cnt==)
printf("-1\n");
else
{
for(int i=;i<=m;i++)
{
if(sccno[x[i]]==sccno[y[i]])
continue;
else
{
indeg[sccno[x[i]]]++;outdeg[sccno[y[i]]]++;
}
}
ll tmpans=;ll ans=;
for(int i=;i<=scc_cnt;i++)
{
if(indeg[i]==||outdeg[i]==)
{
tmpans=;
ll tmp=n-scc[i].size();
tmpans+=(tmp)*(tmp-);
tmpans+=(scc[i].size())*(scc[i].size()-);
tmpans+=(scc[i].size())*tmp;tmpans-=m;
ans=max(ans,tmpans);
}
}
printf("%lld\n",ans);
}
}
}