HDU 1811 判斷有向圖拓撲序唯一性 (UFSet + Tarjan + 拓撲排序)

解法步驟

1. 用并查集合併 "=" 關係的節點。
2. 構建縮點後的 DAG："<" 邊 u→v，">" 邊 v→u。
3. Tarjan 求強連通分量，若同一 SCC 內有邊 → CONFLICT。
4. 對縮點 DAG 拓撲排序 (Kahn 算法)，若某步隊列長度 >1 → UNCERTAIN。
5. 若所有節點入度歸零且無歧義 → OK。

核心代碼結構

// 并查集
int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

// Tarjan
void tarjan(int u) {
    dfn[u]=low[u]=++timer;
    st.push(u); inStack[u]=1;
    for (int v : adj[u]) {
        if (!dfn[v]) { tarjan(v); low[u]=min(low[u], low[v]); }
        else if (inStack[v]) low[u]=min(low[u], dfn[v]);
    }
    if (dfn[u]==low[u]) { /* pop SCC */ }
}

// 拓撲排序判斷唯一性
bool topoUnique() {
    queue q;
    for (int i=1; i<=sccCnt; ++i) if (ind[i]==0) q.push(i);
    while (!q.empty()) {
        if (q.size() > 1) return false; // 不唯一
        int u=q.front(); q.pop();
        for (int v: dag[u]) if (--ind[v]==0) q.push(v);
    }
    return true;
}

複雜度

O(n+m) 每測試用例，n≤30000, m≤100000，完全足夠。