🔗 UVA-11518 Dominos 2

tags: `圖(Graph)` `DFS` `BFS`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

這個問題描述了一個多米諾骨牌倒下的情境。當某一個多米諾骨牌倒下時，它會使接下來的一些多米諾骨牌依次倒下。有時，一個多米諾骨牌未能成功使下一個倒下，此時需要手動擊倒它以繼續連鎖反應。題目的目標是計算給定情況下倒下的多米諾骨牌的總數。

對於每個測試案例，給定三個整數 $n$ 、 $m$ 和 $l$ ，分別表示多米諾骨牌的數量、多米諾骨牌之間的關係數量和需要手動擊倒的多米諾骨牌數量。接下來的 $m$ 行中，每行包含兩個整數 $u$ 和 $v$ ，表示多米諾骨牌 $u$ 倒下時會使多米諾骨牌 $v$ 倒下。最後的 $l$ 行中，每行包含一個整數 $z$ ，表示需要手動擊倒的多米諾骨牌。

計算在 $l$ 個多米諾骨牌被擊倒後，倒下的多米諾骨牌的總數。

思路：DFS / BFS

首先根據題意，可以建立一個有向圖，其中每個多米諾骨牌 $u$ 都有一個鄰接表(Adjacency List) $g[u]$ ，其中包含所有會因為 $u$ 倒下而倒下的多米諾骨牌。

接下來，我們可以使用 DFS 或 BFS 來計算倒下的多米諾骨牌數量。在這裡，我們使用 DFS 來解決問題。使用 DFS 遍歷所有需要手動擊倒的多米諾骨牌，計算倒下的多米諾骨牌數量，並將其加入答案中。但需注意，若擊倒的多米諾骨牌已經倒下，則不計算，因此需要一個陣列 $visited$ 來記錄多米諾骨牌是否已經倒下，並在 DFS 遍歷時將當前多米諾骨牌 $u$ 標記為已倒下。

最後，輸出答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(n+m+l)$ $O (n + m + l)$
- 在每個測試案例中，每個骨牌最多被訪問一次，因此需要 $\mathcal{O}(n)$ 時間。
- 處理輸入的鄰接表需要 $\mathcal{O}(m)$ 時間。
- 若持續推倒已經倒下的多米諾骨牌，則需要 $\mathcal{O}(l)$ 時間。
空間複雜度： $\mathcal{O}(n+m)$ $O (n + m)$
- 有向圖的鄰接表需要 $\mathcal{O}(m)$ 空間。
- 陣列 $visited$ 需要 $\mathcal{O}(n)$ 空間。

t = int(input())

def dfs(u):
    visited[u] = True
    res = 1 # u 倒下
    for v in g[u]:
        if not visited[v]: # v 未倒下
            res += dfs(v)
    return res

for _ in range(t):
    n, m, l = map(int, input().split())
    g = [[] for _ in range(n)]
    
    for _ in range(m):
        u, v = map(int, input().split())
        g[u-1].append(v-1)

    ans = 0
    visited = [False] * n
    for _ in range(l):
        z = int(input())
        if not visited[z-1]:
            ans += dfs(z-1)
    print(ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<vector<int>> g;
vector<bool> visited;

int dfs(int u) {
    visited[u] = true;
    int res = 1;
    for (int v : g[u]) {
        if (!visited[v]) {
            res += dfs(v);
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, n, m, l, u, v, z;
    cin >> t;
    while (t--) {
        cin >> n >> m >> l;
        g.clear();
        g.resize(n);
        for (int i=0; i<m; i++) {
            cin >> u >> v;
            g[u-1].push_back(v-1);
        }
        int ans = 0;
        visited.assign(n, false);
        for (int i=0; i<l; i++) {
            cin >> z;
            if (!visited[z-1]) {
                ans += dfs(z-1);
            }
        }
        cout << ans << endl;
    }
    return 0;
}