您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 2762：從 u 到 v 還是從 v 到 u？——強連通分量縮點與拓撲排序解法

編輯：C++ 入門

問題描述

給定一個有向圖，判斷任意兩個頂點之間是否至少存在一條單向路徑（即從 u 到 v 或從 v 到 u 至少有一條路徑可達）。若圖滿足此性質，輸出 "Yes"，否則輸出 "No"。

解題思路

這是一個經典的強連通分量（SCC）應用題。核心步驟如下：

強連通分量縮點：使用 Tarjan 演算法找出所有強連通分量，將每個強連通分量縮合為一個「超級節點」。縮點後得到一個有向無環圖（DAG）。
拓撲排序驗證：在縮點後的 DAG 上進行拓撲排序。若該 DAG 存在一條哈密頓路徑（即拓撲序列中相鄰兩點之間都有邊相連），則原圖滿足任意兩點單向可達的條件。

關鍵點分析

強連通分量內部任意兩點互相可達，縮點後不影響單向可達性判斷。
縮點圖必須是一條「鏈」：拓撲序列中第 i 個節點必須有邊指向第 i+1 個節點，否則會存在無法單向可達的點對。
題目資料範圍：n ≤ 1000, m ≤ 6000，Tarjan + 拓撲排序的時間複雜度 O(n+m) 完全足夠。

程式碼實現（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

const int MAXN = 1005;
const int MAXM = 100005;

struct Edge { int to, next; } edges[MAXM];
int head[MAXN], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
bool inStk[MAXN], vis[MAXN];
int sccId[MAXN], sccCnt;
vector dag[MAXN];
int inDeg[MAXN];
bool adj[MAXN][MAXN];
int U[MAXM], V[MAXM];

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;
    inStk[u] = true;
    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 (inStk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++sccCnt;
        int v;
        do {
            v = stk[top--];
            inStk[v] = false;
            sccId[v] = sccCnt;
        } while (v != u);
    }
}

bool topoCheck() {
    queue q;
    for (int i = 1; i <= sccCnt; ++i)
        if (inDeg[i] == 0) q.push(i);
    int last = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (last && !adj[last][u]) return false;
        for (int v : dag[u]) {
            if (--inDeg[v] == 0) q.push(v);
        }
        last = u;
    }
    return true;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        // 初始化
        memset(head, 0, sizeof(int)*(n+1));
        memset(dfn, 0, sizeof(int)*(n+1));
        memset(inStk, 0, sizeof(bool)*(n+1));
        memset(vis, 0, sizeof(bool)*(n+1));
        ecnt = idx = top = sccCnt = 0;
        for (int i = 1; i <= sccCnt; ++i) dag[i].clear();
        memset(inDeg, 0, sizeof(int)*(n+1));
        memset(adj, 0, sizeof(bool)*(n+1)*(n+1));

        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &U[i], &V[i]);
            addEdge(U[i], V[i]);
        }

        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i);

        // 建立縮點圖
        for (int i = 1; i <= m; ++i) {
            int u = sccId[U[i]], v = sccId[V[i]];
            if (u != v && !adj[u][v]) {
                adj[u][v] = true;
                dag[u].push_back(v);
                ++inDeg[v];
            }
        }

        puts(topoCheck() ? "Yes" : "No");
    }
    return 0;
}