HDU 4635 強連通分量縮點：最大加邊數不構成強連通圖

題目大意

給定有向圖，求最多能加多少條邊使圖仍不是強連通圖。若原圖已強連通輸出 -1。n, m ≤ 1e5。

解題思路

1. Tarjan 縮點： 求強連通分量 (SCC)，縮成 DAG。設分量數為 `cnt`，每個分量大小 `sz[i]`。
2. 若 `cnt == 1`，原圖強連通，輸出 -1。
3. 統計縮點後 DAG 的入度 `in[i]` 和出度 `out[i]`。
4. 完全圖邊數： `total = n*(n-1) - m` (有向圖無自環重邊)。
5. 要使圖不強連通，必須至少保留一個「源點分量」(入度 0) 或「匯點分量」(出度 0) 之間無路徑。即選一個入度為 0 或出度為 0 的分量 S，禁止從 S 到其補集或補集到 S 的邊。
6. 禁止的邊數 = `sz[S] * (n - sz[S])`。為了最大化可加邊數，需最小化禁止邊數，即選 `sz[S]` 使乘積最小的入度 0 或出度 0 分量。
7. 答案 = `total - min_{in[i]==0 || out[i]==0} (sz[i] * (n - sz[i]))`。

代碼實現 (C++)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 100005;

struct Edge { int to, next; } edges[MAXN * 2];
int head[MAXN], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx, sccCnt;
int bel[MAXN], sz[MAXN];
int inDeg[MAXN], outDeg[MAXN];

void addEdge(int u, int v) {
    edges[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for (int e = head[u]; ~e; e = edges[e].next) {
        int v = edges[e].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (!bel[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++sccCnt;
        int v;
        do { v = stk[top--]; bel[v] = sccCnt; sz[sccCnt]++; } while (v != u);
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        int n, m; scanf("%d%d", &n, &m);
        ecnt = 0; memset(head, -1, sizeof(head));
        for (int i = 0; i < m; i++) {
            int u, v; scanf("%d%d", &u, &v);
            addEdge(u, v);
        }
        memset(dfn, 0, sizeof(dfn));
        memset(bel, 0, sizeof(bel));
        memset(sz, 0, sizeof(sz));
        idx = top = sccCnt = 0;
        for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
        
        if (sccCnt == 1) {
            printf("Case %d: -1\n", tc);
            continue;
        }
        
        memset(inDeg, 0, sizeof(inDeg));
        memset(outDeg, 0, sizeof(outDeg));
        for (int u = 1; u <= n; u++) {
            for (int e = head[u]; ~e; e = edges[e].next) {
                int v = edges[e].to;
                if (bel[u] != bel[v]) {
                    outDeg[bel[u]]++;
                    inDeg[bel[v]]++;
                }
            }
        }
        
        LL total = 1LL * n * (n - 1) - m;
        LL ban = 1LL << 60;
        for (int i = 1; i <= sccCnt; i++) {
            if (inDeg[i] == 0 || outDeg[i] == 0) {
                ban = min(ban, 1LL * sz[i] * (n - sz[i]));
            }
        }
        printf("Case %d: %lld\n", tc, total - ban);
    }
    return 0;
}

關鍵證明

在 DAG 中，若選一個入度為 0 的分量 S，則無邊能進入 S。若我們添加所有除 `S → V\S` 以外的邊，圖仍不強連通（因 S 無法被到達）。這樣少加了 `sz[S]*(n-sz[S])` 條邊。同理出度為 0 的分量。為了最大化可加邊數，選擇使此乘積最小的分量。