[백준] 1717번 집합의 표현
문제 링크
문제 설명
-
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다
-
0, a, b 일 때, a가 속한 집합과 b가 속한 집합을 합한다
-
1, a, b 일 때, a가 속한 집합과 b가 속한 집합이 같은지 출력
틀린 풀이
- 그대로 구현
- 시간초과
- 합집합 -> 에지 연결 -> DFS
- 시간초과
- 특정 좌표를 찾아야만 재귀가 종료하기 때문?
- 루트가 같기만 하면 같은 집합
맞은 풀이
-
각 수마다 부모 노드를 저장하는 리스트 생성
-
1, a, b 일 때
- a와 b의 루트 노드를 각각 찾는다
- 같으면 yes, 다르면 no
-
0, a, b 일 때
-
a와 b의 루트 노드를 각각 찾는다
-
다를 경우
- a의 루트 노드의 부모 = b의 루트 노드 (순서 무관)
Union 과정
- 0 1 3 결과
- 0 7 6 결과
- 0 3 7 결과
- 0 4 2 결과
코드
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)
Author And Source
이 문제에 관하여([백준] 1717번 집합의 표현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1717번-집합의-표현
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
-
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다
-
0, a, b 일 때, a가 속한 집합과 b가 속한 집합을 합한다
-
1, a, b 일 때, a가 속한 집합과 b가 속한 집합이 같은지 출력
틀린 풀이
- 그대로 구현
- 시간초과
- 합집합 -> 에지 연결 -> DFS
- 시간초과
- 특정 좌표를 찾아야만 재귀가 종료하기 때문?
- 루트가 같기만 하면 같은 집합
맞은 풀이
-
각 수마다 부모 노드를 저장하는 리스트 생성
-
1, a, b 일 때
- a와 b의 루트 노드를 각각 찾는다
- 같으면 yes, 다르면 no
-
0, a, b 일 때
-
a와 b의 루트 노드를 각각 찾는다
-
다를 경우
- a의 루트 노드의 부모 = b의 루트 노드 (순서 무관)
Union 과정
- 0 1 3 결과
- 0 7 6 결과
- 0 3 7 결과
- 0 4 2 결과
코드
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)
Author And Source
이 문제에 관하여([백준] 1717번 집합의 표현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1717번-집합의-표현
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 시간초과
- 시간초과
- 특정 좌표를 찾아야만 재귀가 종료하기 때문?
- 루트가 같기만 하면 같은 집합
-
각 수마다 부모 노드를 저장하는 리스트 생성
-
1, a, b 일 때
- a와 b의 루트 노드를 각각 찾는다
- 같으면 yes, 다르면 no
-
0, a, b 일 때
-
a와 b의 루트 노드를 각각 찾는다
-
다를 경우
- a의 루트 노드의 부모 = b의 루트 노드 (순서 무관)
-
Union 과정
- 0 1 3 결과
- 0 7 6 결과
- 0 3 7 결과
- 0 4 2 결과
코드
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)
Author And Source
이 문제에 관하여([백준] 1717번 집합의 표현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1717번-집합의-표현
저자 귀속: 원작자 정보가 원작자 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)
Author And Source
이 문제에 관하여([백준] 1717번 집합의 표현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-1717번-집합의-표현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)