hdu 4635 Strongly connected(强连通+缩点)

n个点，m条边的有向图，求最多能增加多少条边，原图任然不是强连通图。

将问题转化为，n个点的完全图，共有n*(n-1)条边，除去原有的m条边，最少删多少条边，使得该图不是强连通图？

求出scc后缩点得到scc图，对于一个scc点，如果他的入度为0，那么只需在完全图中，删去所有指向该强连通分量的边就行了，对于出度为0的scc点也是如此。而要求最大的可加边数，只需求出入度或者出度为0的点权最小的那个scc就行，答案便是n*(n-1) - m - sum[_scc] * (n-sum[_scc]) 。

    #include<iostream>

#include<algorithm>

#include<vector>

#include<string>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<fstream>

#include<sstream>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define LL long long

#define PB push_back

#define debug puts("**debug**")

using namespace std;



const int maxn = 100001;

int n, m, u, v;

int pre[maxn], low[maxn], dfs_clock, scc_cnt, sccno[maxn], in[maxn], out[maxn],  sum[maxn];

vector<int> G[maxn];

stack<int> S;



void dfs(int u)

{

    pre[u] = low[u] = ++dfs_clock;

    S.push(u);

    REP(i, G[u].size())

    {

        int v = G[u][i];

        if(!pre[v])

        {

            dfs(v);

            low[u] = min(low[u], low[v]);

        }

        else if(!sccno[v]) low[u] = min(low[u], pre[v]);

    }

    if(low[u] == pre[u])

    {

        scc_cnt++;

        for(;;)

        {

            int x = S.top(); S.pop();

            sccno[x] = scc_cnt;

            if(x == u) break;

        }

    }

}



void find_scc()

{

    dfs_clock = scc_cnt = 0;

    CLR(pre, 0); CLR(sccno, 0); CLR(in, 0); CLR(out, 0); CLR(sum, 0);

    FF(i, 1, n+1) if(!pre[i]) dfs(i);

}



int main()

{

    int T; scanf("%d", &T);

    FF(kase, 1, T+1)

    {

        scanf("%d%d", &n, &m);

        FF(i, 1, n+1) G[i].clear();

        REP(i, m)

        {

            scanf("%d%d", &u, &v);

            G[u].PB(v);

        }

        find_scc();

        printf("Case %d: ", kase);

        if(scc_cnt == 1)

        {

            puts("-1");

            continue;

        }

        LL ans = n*(n-1) - m;

        FF(u, 1, n+1)

        {

            sum[sccno[u]]++;

            REP(i, G[u].size())

            {

                int v = G[u][i];

                if(sccno[u] != sccno[v]) out[sccno[u]]++, in[sccno[v]]++;

            }

        }

        int tmp = 1e9;

        FF(i, 1, scc_cnt+1)

            if(in[i] == 0 || out[i] == 0) tmp = min(tmp, sum[i]);

        ans -= tmp*(n-tmp);

        printf("%lld\n", ans);

    }

    return 0;

}
  

hdu 4635 Strongly connected(强连通+缩点)