卡碼網 107 尋找存在的路徑
初識并查集
并查集功能：
- 尋找根節點，函數: find(int u)，也就是判斷這個節點的祖先節點是哪個
- 將兩個節點接入到同一個集合，函數: join(int u, int v)，將兩個節點連在同一個根節點上
- 判斷兩個節點是否在同一個集合，函數: isSame(int u, int v)，就是判斷兩個節點是不是同一個根節點
class UnionFind:def __init__(self, size):self.parent = list(range(size + 1))def find(self, u):if self.parent[u] != u:self.parent[u] = self.find(self.parent[u])return self.parent[u]def union(self, u, v):root_u = self.find(u)root_v = self.find(v)if root_u != root_v:self.parent[root_v] = root_udef is_same(self, u, v):return self.find(u) == self.find(v)def main():import sysinput = sys.stdin.readdata = input().split()index = 0n = int(data[index])index += 1m = int(data[index])index += 1uf = UnionFind(n)for _ in range(m):s = int(data[index])index += 1t = int(data[index])index += 1uf.union(s, t)source = int(data[index])index += 1destination = int(data[index])if uf.is_same(source, destination):print(1)else:print(0)if __name__ == '__main__':main()
)
)
