HDU - 4635 Strongly connected

Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the graph is still a simple directed graph. Also, after you add these edges, this graph must NOT be strongly connected.

A simple directed graph is a directed graph having no multiple edges or graph loops.

A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.

Input

The first line of date is an integer T, which is the number of the text cases.

Then 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 lines follow. Each line contains two integers x and y, means that there is a edge from x to y.

Output

For each case, you should output the maximum number of the edges you can add.

If the original graph is strongly 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      

題意：給定一個圖，求在不成為強連通的條件下最多能添加多少條邊。如果本來就是連通圖，輸出-1.

思路：先用tarjan縮點。不成為強連通，隻需要一個點被孤立（不能形成回路），其他點全部連接配接。這個被孤立的點需要縮點中的點盡量少，且需要入度或者出度為零。假設被最少的縮點中有p個點，則其他可以任意連接配接的點為di=n-p。di個點一共可以連接配接di*（di-1）條邊，最少縮點中要隻能進或則隻能出（入度為零或出度為零）。是以最少縮點裡面的點也可以任意連接配接，總數為p*(p-1)。被孤立的點連接配接其他點（隻進或隻出），一共有p*n條，則總數為：di*（di-1）+p*(p-1)+p*n。然後減去題目給出的邊數m就是答案。

#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<stack>
#define M 100010
using namespace std;
struct path
{
    int to,nextt;
}A[M];
stack<int>q;
int head[M],DFN[M],LOW[M],book[M],re[M],in[M],out[M],sum[M];
int t,ph=0,n,m,x,y,tot,carry,indox;
void init()
{
    tot=carry=indox=0;
    memset(in,0,sizeof(in));
    memset(head,-1,sizeof(head));
    memset(book,0,sizeof(book));
    memset(DFN,-1,sizeof(DFN));
    memset(LOW,-1,sizeof(LOW));
    memset(out,0,sizeof(out));
    memset(sum,0,sizeof(sum));
    return ;
}
void add(int u,int v)
{
    A[tot].to=v;
    A[tot].nextt=head[u];
    head[u]=tot++;
    return ;
}
void tarjan(int u)
{
    int tem;
    DFN[u]=LOW[u]=++indox;
    book[u]=1;
    q.push(u);
    for(int i=head[u];i!=-1;i=A[i].nextt)
    {
        tem=A[i].to;
        if(DFN[tem]==-1)
        {
            tarjan(tem);
            LOW[u]=min(LOW[u],LOW[tem]);
        }
        else if(book[tem])
        {
            LOW[u]=min(LOW[u],DFN[tem]);
        }
    }
    if(DFN[u]==LOW[u])
    {
        ++carry;
        do
        {
            tem=q.top();
            q.pop();
            book[tem]=0;
            re[tem]=carry;
        }while(tem!=u);
    }
    return ;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        for(int i=1;i<=n;i++)
        {
            if(DFN[i]==-1)
                tarjan(i);
        }
        printf("Case %d: ",++ph);
        if(carry==1)
        {
            printf("-1\n");
            continue;
        }
        int v;
        for(int i=1;i<=n;i++)
        {
            sum[re[i]]++;
            for(int j=head[i];j!=-1;j=A[j].nextt)
            {
                v=A[j].to;
                if(re[i]!=re[v])
                {
                    in[re[v]]++;
                    out[re[i]]++;
                }
            }
        }
        int pan=0x3f3f3f3f,k;
        for(int i=1;i<=carry;i++)
        {
            if(pan>sum[i]&&(in[i]==0||out[i]==0))
            {
                pan=sum[i];
                k=i;
            }
        }
        int di=n-pan;
        int ans=di*(di-1)+di*pan-m+pan*(pan-1);
        printf("%d\n",ans);
    }
}