连通专题 加最多的边 使 图仍然非强连通图

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4635
题目大意：给一个n个点的简单有向图，问最多能加多少条边使得该图仍然是简单有向图，且不是强连通图。简单有向图定义：没有重边，无自环。如果一开始就是一个强连通图，则输出-1。

思路：边最多应该是完全图，有向图的完全图有(n)*(n-1)条边。但是边应该尽量多，那么最后只剩下两个强连通分量时边应该是最多的。
缩点后：

这里WA了，因为我把点最少的强连通分量，作为点1。这里(x) * (n-x)的值，不是x越小就越小，是个二次函数。并且没有考虑入度与出度。因为只有入度或者出度=0，才能作为点1。

#include<bits/stdc++.h>

using namespace std;
const int maxn=2e5+5;
vector<int> v[maxn];

int dfn[maxn];//dfs第一次的时间戳
int low[maxn];//能到达的最远祖先(时间戳最小)
int vis[maxn];//是否在栈中
long long  tot, n, m;

int R[maxn], C[maxn];//强连通分量缩点的入度和出度
int scc[maxn]={0};   //保存所有的点属于哪个强连通分量
int F[maxn]={0};     //第i个强连通分量包含点的个数
int N=0;             //N个强连通分量

stack<int> s;
void Tarjn(int x)
{
    low[x]=dfn[x]=++tot;//每次dfs，x的次序号增加1
    s.push(x), vis[x]=1;//将x入栈 标记x在栈内
    for(int i=0;i<v[x].size();i++)//访问从x出发的边
    {
        int u=v[x][i];
        if(!dfn[u])     //如果u没被访问过
        {
            Tarjn(u);   //dfs(v)
            low[x]=min(low[x], low[u]);//x点和x的子树能到达的最远祖先(最小dfn)
        }
        else if(vis[u]) //u在栈中
        {
            low[x]=min(low[x], dfn[u]);//u点能到达的最小次序号是它自己能到达点的最小次序号和u的次序号中较小的
        }
    }
    if(low[x]==dfn[x])  //x为强连通的根
    {
        N++;//
        while(1)
        {
            int now=s.top();
            s.pop();
            scc[now]=N;//
            F[N]++;    //
            vis[now]=0;
            if(now==x)  //把这个强连通分量全部退出栈
            {
                break;
            }
        }
    }
}

void dfs()              //缩点
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(scc[i]!=scc[v[i][j]])
            {
                C[scc[i]]++;
                R[scc[v[i][j]]]++;
            }
        }
    }
}

int main()
{
    int t, W=0;
    scanf("%d",&t);
    while(t--)
    {
        W++;
        for(int i=1;i<=maxn;i++)
        {
            v[i].clear();
        }
        memset(scc, 0, sizeof(scc));
        N=0;
        memset(C, 0, sizeof(R));
        memset(R, 0, sizeof(R));
        memset(F, 0, sizeof(F));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(vis, 0, sizeof(vis));
        tot=0;
        memset(vis, 0, sizeof(vis));
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x, y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                Tarjn(i);
            }
        }

        dfs();

        long long ans=0;
        cout<<"Case "<<W<<":"<<" ";
        if(N==1)
        {
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=N;i++)
        {
            if(R[i]==0||C[i]==0)
            {
                ans=max(ans, (n)*(n-1)-((long long)F[i])*(n-F[i])-m);
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}