HDU 4635 Strongly connected

http://acm.hdu.edu.cn/showproblem.php?pid=4635
Strongly connected
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：1337    Acceepted Submission(s)：566
Problem Description
Give a simple directed graph with N nodes.Please tell me the maximnumber of the edges You can add that the graph is still a simple directed graph.Also，after you add theedges，this strectront.apt.apt.apt.ort。
A simple directed graph is a directed graphed havingのmultile edges or graphh loops.A stronigly connected digraph is a directed graph inch it is possible to reach any node starting from any her nobytratch thereedictures。 
 
Input
The first line of date is an integer T，which is the number of the text cases.
The n T cases follow、each case starts of two numbers N and M、1<=N==100000、1<=M==100000、representing the number of nodes and the number of edges、then M lineas follow.Each line containtments the the the me me me me me me me me me me me me me me andatttwith、and
 
Output
For each case，you Shouuld output the maximnumber of the edges you can add.
If theオリジナリティgraph is strogly connected、just output-1.
 
Sample Input

   
   
   
   

    
    
    
    3
3 3
1 2
2 3
3 1
3 3
1 2
2 3
1 3
6 6
1 2
2 3
3 1
4 5
5 6
6 4
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case 1: -1
Case 2: 1
Case 3: 15
   
   
   
   

 
ソurce
2013 Multi-University Training Conteest 4
 
 
最終的に辺の図を追加したら、必ず二つの部XとYに分けられます。その中にXからYまでの辺はYからXまでの辺がないので、辺をできるだけ多く数えてもいいです。X部は完全図に違いないです。Y部も同じです。X部にはそれぞれの点が一つあります。X部にはx点があります。Y部にはy点があります。整理：F=N*N-N-x*yはx+yが定値であれば近いほどx*yが大きくなりますので、辺数が一番多くなるとX部とY部の点数の個数の差が大きくなりますので、まず与えられた点に対して縮小点があります。縮点後の各点について、もしその出度や入度が0なら、X部またはY部になります。したがって、ノード数が一番少ない点を含み、他の全ての点を合わせてもう一つの部分にすると、最大辺数の図が得られます。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define prt(k) cout<<#k"="<<k<<endl;
#define ll long long
#include<vector>
#define N 100053
int belong[N],dfn[N],low[N];
vector<int> g[N];
#include<stack>
int scc,curr;
stack<int> S;
bool instack[N];
vector<int> color[N],G1[N],G2[N];
int n,m;
void dfs(int u)
{
    dfn[u]=low[u]=++curr;
    S.push(u);
    instack[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!dfn[v]) {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else {
            if(instack[v])
                low[u]=min(low[u],dfn[v]);
        }

    }
    if(low[u]==dfn[u]) {
            ++scc;  int v;
            do {
                v=S.top(); S.pop();
                color[scc].push_back(v);
                instack[v]=0;
                belong[v]=scc;
            }while(v!=u);
        }
}
int main()
{
    int tt; cin>>tt;    int ca=1;
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) g[i].clear(),G1[i].clear(),G2[i].clear(),color[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
        }
        memset(dfn,0,sizeof dfn);
        memset(instack,0,sizeof instack);
        while(!S.empty()) S.pop();
        scc=0;   curr=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i])
            dfs(i);
       /// prt(scc);
        printf("Case %d: ",ca++);
        if(scc==1)
        {
            puts("-1");
            continue;
        }
        for(int u=1;u<=n;u++)
        {
            for(int i=0;i<g[u].size();i++)
            {
                int v=g[u][i];
                int a=belong[u],b=belong[v];
              ///  prt(a); prt(b);
                if(a!=b) G1[a].push_back(b),G2[b].push_back(a);
              ///  puts("=======");
            }
        }
        int X=n;
        for(int i=1;i<=scc;i++)
            if(G1[i].size()==0||G2[i].size()==0)
        {
            X=min(X,(int)color[i].size());
        }
        ll ans=1ll*n*n-n-1ll*X*(n-X)-m;
        printf("%I64d
",ans);
    }
}