hdu 4635 Strongly connected(Tarjan)

做完後，看了解題報告，思路是一樣的。我就直接粘過來吧

最終添加完邊的圖，肯定可以分成兩個部X和Y，其中只有X到Y的邊沒有Y到X的邊，那麼要使得邊數盡可能的多，則X部肯定是一個完全圖，Y部也是，同時X部中每個點到Y部的每個點都有一條邊，假設X部有x個點，Y部有y個點，有x+y=n，同時邊數F=x*y+x*(x-1)+y*(y-1)，整理得：F=N*N-N-x*y，當x+y為定值時，二者越接近，x*y越大，所以要使得邊數最多，那麼X部和Y部的點數的個數差距就要越大，所以首先對於給定的有向圖縮點，對於縮點後的每個點，如果它的出度或者入度為0，那麼它才有可能成為X部或者Y部，所以只要求縮點之後的出度或者入度為0的點中，包含節點數最少的那個點，令它為一個部，其它所有點加起來做另一個部，就可以得到最多邊數的圖了

//109MS 	2916KB
#include <stdio.h>
#include <string.h>
#define LL long long
const int M = 100005;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int to,nxt;
} edge[M];

int head[M],low[M],dfn[M],stack[M+10];
int vis[M],out[M],in[M],belong[M];
int scc,cnt ,top,ep;
LL n,m;
int min (int a,int b)
{
    return a > b ? b : a;
}
void addedge (int cu,int cv)
{
    edge[ep].to = cv;
    edge[ep].nxt = head[cu];
    head[cu] = ep ++;
}

void Tarjan(int u)
{
    int v;
    dfn[u] = low[u] = ++cnt;
    stack[top++] = u;
    vis[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].nxt)
    {
        v = edge[i].to;
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if (vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++scc;
        do
        {
            v = stack[--top];
            vis[v] = 0;
            belong[v] = scc;
        }
        while (u != v);
    }
}

void solve()
{
    int u,v;
    scc = top = cnt = 0;
    memset (vis,0,sizeof(vis));
    memset (dfn,0,sizeof(dfn));
    memset (out,0,sizeof(out));
    memset (in,0,sizeof(in));
    for (u = 1; u <= n; u ++)
        if (!dfn[u])
            Tarjan(u);

    for (u = 1; u <= n; u ++)
    {
        for (int i = head[u]; i != -1; i =edge[i].nxt)
        {
            v = edge[i].to;
            if (belong[u] != belong[v])
            {
                out[belong[u]] ++;
                in[belong[v]] ++;
            }
        }
    }
    int num[M],Min;
    memset (num,0,sizeof(num));
    for (u = 1; u <= n; u ++)
        if (!in[belong[u]]) num[belong[u]] ++;
    for (u = 1; u <= scc; u ++)
        if (num[u]!= 0&&num[u]<Min)
            Min = num[u];

    memset (num,0,sizeof(num));
    for (u = 1; u <= n; u ++)
        if (!out[belong[u]]) num[belong[u]] ++;
    for (u = 1; u <= scc; u ++)
        if (num[u]!= 0&&num[u]<Min)
            Min = num[u];
    if (scc == 1)
    {
        printf ("-1\n");
        return ;
    }
    LL ans = n*(n-1)-Min*(n-Min) - m;
    printf ("%I64d\n",ans);
}
int main ()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T,u,v,cnt = 0;
    scanf ("%d",&T);
    while (T --)
    {
        scanf ("%I64d%I64d",&n,&m);
        ep = 0;
        memset (head,-1,sizeof(head));
        for (int i = 0; i < m; i++)
        {
            scanf ("%d%d",&u,&v);
            addedge(u,v);
        }
        printf ("Case %d: ",++cnt);
        solve();
    }
    return 0;
}