股票追蹤問題：檢測循環持股鏈的拓撲排序與並查集解法

問題描述

N 家公司，T 筆交易 (A 買 B 股份)。若交易導致某公司間接控股自己 (形成環)，則拒絕該交易。輸出被拒絕交易數。

建模

有向圖：節點=公司，邊 A→B 表示 A 持有 B 股份。檢測加邊後是否出現環。

並查集解法 (Union-Find)

由於只需檢測「是否形成環」，可用並查集維護連通分量。但注意：有向圖環檢測通常用 DFS 拓撲序或 Tarjan，並查集適用於無向圖。本題中「控股」關係可視為無向連通性 (若 A 持 B 且 B 持 A 即互相持股)，但題目實為有向遞歸控股。

正確做法：拓撲排序 / DFS 環檢測

// 簡化：每次加邊前做 DFS 檢測從 B 能否達到 A
bool dfs(int u, int target, vector adj[], vector& vis) {
    if (u == target) return true;
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v] && dfs(v, target, adj, vis)) return true;
    return false;
}

// 主循環
int rejected = 0;
for each transaction (A, B):
    if (dfs(B, A, adj, vis)) rejected++;
    else adj[A].push_back(B); // 接受交易

複雜度

T ≤ 100,000，N ≤ 234。每次 DFS O(N+E) 可能超時。優化：維護傳遞閉包 (Floyd-Warshall O(N³) 約 1.2e7 可接受) 或使用動態拓撲序算法。

參考

Stock Chase 詳細解析