BZOJ 2438 殺人遊戲：Tarjan 強連通分量縮點求最優查證策略

問題背景

N 個人中藏有一名殺手，警察可查證任意一人。查證平民會獲得其認識的人的身份信息；查證殺手則遊戲失敗。每人是殺手概率均等。目標：在保證警察安全前提下，最大化確定殺手的概率。

核心洞察：概率轉化為最小查證集

若警察需查證 x 人才能確定殺手，則安全概率 = 1 - x/N。因為殺手均勻分布，查證 x 人不包含殺手的概率即為 (N-x)/N。關鍵在於求最少需查證多少人。

圖論建模與縮點

• 有向邊 x→y 表示 x 認識 y。
• 若查證某人，可獲得其所有出邊指向節點的信息。
• 強連通分量 (SCC) 內任意節點可相互到達，查證其中任一節點等價於查證整個 SCC。故可用 Tarjan 算法將 SCC 縮點，形成 DAG。

DAG 上的最優策略

縮點後的 DAG 中，入度為 0 的節點 (源點) 必須被查證，因為無其他節點能提供其信息。答案初步為：1 - (源點數 / N)。

特殊優化：最後一個孤立節點

若存在入度為 0 且出度指向的節點入度 > 1 的源點（即其信息可被其他途徑間接獲得），則該節點可作為最後推斷，無需直接查證。此時源點數 -1，概率提升。

完整算法流程

1. 讀入圖，構建鄰接表。
2. Tarjan 算法求 SCC，縮點得到 DAG，記錄每個 SCC 的大小。
3. 統計縮點圖中每個 SCC 的入度。
4. 遍歷所有 SCC，滿足 to[i]==i && in[i]==0 為源點，計數 s。
5. 檢查是否存在「可省略的源點」：入度 0、大小 1、所有出邊指向入度 > 1 的節點。若存在，s--。
6. 答案 = 1.0 - (double)s / N，保留 6 位小數。

Tarjan 核心代碼片段

int dfn[N], low[N], stk[N], top, idx, scc_cnt;
int belong[N], scc_size[N];
bool in_stk[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u; in_stk[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[top--];
            in_stk[v] = false;
            belong[v] = scc_cnt;
            scc_size[scc_cnt]++;
        } while (v != u);
    }
}

完整參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010, MAXM = 300010;

struct Edge { int to, next; } e[MAXM];
int head[MAXN], ecnt;
int n, m;

int dfn[MAXN], low[MAXN], stk[MAXN], top, idx, scc_cnt;
int belong[MAXN], scc_size[MAXN];
bool in_stk[MAXN];
int in_deg[MAXN];

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

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u; in_stk[u] = true;
    for (int i=head[u]; i; i=e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[top--];
            in_stk[v] = false;
            belong[v] = scc_cnt;
            scc_size[scc_cnt]++;
        } while (v != u);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        add_edge(u, v);
    }
    for (int i=1; i<=n; ++i) if (!dfn[i]) tarjan(i);

    // 縮點建圖、統計入度
    for (int u=1; u<=n; ++u) {
        for (int i=head[u]; i; i=e[i].next) {
            int v = e[i].to;
            if (belong[u] != belong[v]) in_deg[belong[v]]++;
        }
    }

    int source_cnt = 0;
    bool can_reduce = false;
    for (int i=1; i<=scc_cnt; ++i) {
        if (in_deg[i] == 0) {
            source_cnt++;
            // 檢查是否為可省略的單點源點
            if (!can_reduce && scc_size[i] == 1) {
                bool all_out_deg_gt1 = true;
                // 找到該SCC對應的原圖節點
                int u = 0;
                for (int j=1; j<=n; ++j) if (belong[j]==i) { u=j; break; }
                for (int k=head[u]; k; k=e[k].next) {
                    if (in_deg[belong[e[k].to]] == 1) { // 唯一入邊來自自身
                        all_out_deg_gt1 = false; break;
                    }
                }
                if (all_out_deg_gt1) can_reduce = true;
            }
        }
    }

    double ans = 1.0 - (double)(source_cnt - can_reduce) / n;
    printf("%.6f\n", ans);
    return 0;
}

複雜度與總結

• 時間：O(N+M) Tarjan + O(N+M) 縮點統計，線性複雜度。
• 空間：O(N+M)。
• 關鍵點：SCC 縮點將環內節點等價化；DAG 源點對應必查集合；孤立單點源點可通過反推省略。

此題巧妙將概率問題轉化為圖論最小覆蓋問題，展示了 Tarjan 算法在實際建模中的強大應用能力。