最小全域木(MST)については以下:
最小全域木(MST - Minimum Spanning Tree) - 競プロはじめました
UnionFindについては以下:
UnionFind木 - 競プロはじめました
考え方
クラスカル法を使う.以下のようにすれば良い.一度のクラスカル法でクエリ全ての答えを求める.
- $G$とクエリに含まれるすべての辺をコストの小さい順にソートし,コストの小さい順に辺を見ていく.
- 見ている辺がマージされていないされていない場合,
- クエリに含まれる辺なら,このクエリの答えが'Yes'となることを保存して,マージせずに次へ
- クエリに含まれない辺なら,マージして次へ
回答例
N, M, Q = map(int, input().split()) edge = [] for _ in range(M): a, b, c = map(int, input().split()) edge.append((c, a, b, -1)) for q in range(Q): u, v, w = map(int, input().split()) edge.append((w, u, v, q)) edge.sort() # --- UnionFind --- p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def unite(x, y): x = root(x) y = root(y) if x == y: return p[y] = x # --- UnionFind --- ans = ['No'] * Q for c, a, b, i in edge: if root(a) != root(b): if i != -1: ans[i] = 'Yes' else: unite(a, b) print(*ans, sep = '\n')
【参考】Submission #28546576 - HHKB Programming Contest 2022(AtCoder Beginner Contest 235)