思路：想用Tarjan算法进行缩点，并记录每个连通分支的点数。缩点完毕过后，找出所有出度或入度为0的连通分量，假设该连通分量的点数为num[i]，那么
ans=Max(ans,(n-num-1)*(n-num)+(num-1)*num+(n-num)*num-m)；
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define Maxn 100010 #define Max(a,b) (a)>(b)?(a):(b) using namespace std; int head[Maxn],vi[Maxn],dfn[Maxn],low[Maxn],e,lab,top,Stack[Maxn],flag,id[Maxn],in[Maxn],out[Maxn],n,m,Ei[Maxn],num; __int64 ans; struct Edge{ int u,v,next; }edge[Maxn]; void init() { memset(head,-1,sizeof(head)); memset(vi,0,sizeof(vi)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(Ei,0,sizeof(Ei)); e=lab=top=flag=num=0; ans=0; } void add(int u,int v) { edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } void Tarjan(int u) { dfn[u]=low[u]=++lab; vi[u]=1; Stack[top++]=u; int i,j,v; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++num; int cnt=0; do{ i=Stack[--top]; vi[i]=0; id[i]=num; cnt++; }while(i!=u); Ei[num]=cnt; if(n==cnt) { flag=1; return ; } } } int solve() { int i,j; for(i=1;i<=n;i++) { if(!dfn[i]) Tarjan(i); if(flag) return 0; } return 1; } int main() { int i,j,a,b,t,Case=0; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); } if(!solve()||flag) { printf("Case %d: -1 ",++Case); continue; } for(i=1;i<=n;i++) for(j=head[i];j!=-1;j=edge[j].next) { int u=edge[j].u; int v=edge[j].v; if(id[u]!=id[v]) { in[id[v]]++; out[id[u]]++; } } __int64 temp; for(i=1;i<=num;i++) if(in[i]==0||out[i]==0) { temp=(__int64)((n-Ei[i])*(n-Ei[i]-1)+Ei[i]*(Ei[i]-1)+(n-Ei[i])*Ei[i]-m); ans=Max(ans,temp); } printf("Case %d: %I64d ",++Case,ans); } return 0; }