[白俊]1717号集合の表現
6331 ワード
質問リンク
問題の説明
初期{0}、{1}、{2}、...n+1個の集合をそれぞれ構成する
0、a、bの場合、aの属する集合とbの属する集合を加算
1、a、bの場合、aが属する集合とbが属する集合とが同一か否かを出力する
エラーの回答
対草
各ノードに複数の親ノードが格納されるリストを作成します.
1、a、bの場合
0、a、bの場合
aとbのルートノードを別々に検索
場合によって
Unionコース
コード#コード# import sys
def union(a, b):
ra = get_root(a)
rb = get_root(b)
if ra != rb:
parent[rb] = ra
def get_root(x):
if parent[x] != x:
parent[x] = get_root(parent[x])
return parent[x]
sys.setrecursionlimit(10000)
ipt = sys.stdin.readline
opt = sys.stdout.write
n, m = map(int, ipt().split())
parent = list(range(n+1))
for _ in range(m):
check, a, b = map(int, ipt().split())
if a > b:
a, b = b, a
if check:
ra = get_root(a)
rb = get_root(b)
if ra == rb:
opt('yes\n')
else:
opt('no\n')
else:
union(a, b)
Reference
この問題について([白俊]1717号集合の表現), 我々は、より多くの情報をここで見つけました
https://velog.io/@leehj8896/백준-1717번-집합의-표현
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
def union(a, b):
ra = get_root(a)
rb = get_root(b)
if ra != rb:
parent[rb] = ra
def get_root(x):
if parent[x] != x:
parent[x] = get_root(parent[x])
return parent[x]
sys.setrecursionlimit(10000)
ipt = sys.stdin.readline
opt = sys.stdout.write
n, m = map(int, ipt().split())
parent = list(range(n+1))
for _ in range(m):
check, a, b = map(int, ipt().split())
if a > b:
a, b = b, a
if check:
ra = get_root(a)
rb = get_root(b)
if ra == rb:
opt('yes\n')
else:
opt('no\n')
else:
union(a, b)Reference
この問題について([白俊]1717号集合の表現), 我々は、より多くの情報をここで見つけました https://velog.io/@leehj8896/백준-1717번-집합의-표현テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol