ZeroJudge 解題筆記：r775.Let's go on a trip

作者：王一哲
日期：2026年9月9日


ZeroJudge 題目連結：r775.Let's go on a trip

解題想法

題目第一列給一個整數 $n$，代表共有 $n$ 座城市，編號為 $1$ 到 $n$。第二列給一個整數 $m$，代表要走訪 $m$ 座城市。接下有 $n$ 列，每列 $n$ 個數字，第 $i$ 列、第 $j$ 欄如果是 $1$，代表城市 $i, j$ 之間有道路連接，題目保證 $j, i$ 之間也有道路連接；反之，如果數字為 $0$，代表城市 $i, j$ 之間沒有道路連接。最後一列有 $m$ 個整數，代表要走訪的城市編號。這題只要回答是否能走訪這 $m$ 個城市，同一個城市可以多次走訪。

可以將城市當成節點，道路當成邊，只要檢查最後一列的城市是否相連，這樣的題目很適合用併查集處理。我習慣用 class 自訂併查集物件，這次在 class 之中再自訂一個函式 is_unite，檢查代入的兩個節點是否連通。先取第一個要走訪的城市，以這個城市的父節點 $root$ 為準，如果其它要走訪的城市父節點不是 $root$，答案為 NO；如果這 $m$ 個城市的父節點都是 $root$，答案為 YES。

Python 程式碼

使用時間約為 32 ms，記憶體約為 10.1 MB，通過測試。

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.sz = [1] * (n + 1)
    
    def rfind(self, x):
        if x == self.parent[x]:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]
    
    def unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.sz[root_u] < self.sz[root_v]:
                root_u, root_v = root_v, root_u
            self.sz[root_u] += self.sz[root_v]
            self.parent[root_v] = root_u
            return True
        return False

    def is_unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        return root_u == root_v

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr + 1])
        ptr += 2
        dsu = DisjointSetUnion(n)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                x = int(data[ptr])
                ptr += 1
                if x == 1:
                    dsu.unite(i, j)
        
        ans = True
        root = int(data[ptr])
        ptr += 1
        for _ in range(m - 1):
            x = int(data[ptr])
            ptr += 1
            if not dsu.is_unite(root, x):
                ans = False
                break
        result.append("YES\n" if ans else "NO\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 4 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

class DisjointSetUnion {
private:
    vector<int> parent, sz;

public:
    DisjointSetUnion(int x) {
        parent.resize(x + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(x + 1, 1);
    }

    int rfind(int x) {
        if (x == parent[x]) return x;
        parent[x] = rfind(parent[x]);
        return parent[x];
    }
    
    bool unite(int u, int v) {
        int root_u = rfind(u), root_v = rfind(v);
        if (root_u != root_v) {
            if (sz[root_u] < sz[root_v]) {
                swap(root_u, root_v);
            }
            sz[root_u] += sz[root_v];
            parent[root_v] = root_u;
            return true;
        }
        return false;
    }

    bool is_unite(int u, int v) {
        int root_u = rfind(u), root_v = rfind(v);
        return root_u == root_v;
    }
};

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        int m; scanf("%d", &m);
        DisjointSetUnion dsu (n + 1);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                int x; scanf("%d", &x);
                if (x == 1) dsu.unite(i, j);
            }
        }
        
        bool ans = true;
        int root; scanf("%d", &root);
        for(int i = 0; i < m-1; i++) {
            int x; scanf("%d", &x);
            if (!dsu.is_unite(root, x)) {
                ans = false;
                break;
            }
        }

        if (ans) puts("YES");
        else puts("NO");
    }
    return 0;
}