백준
1. 서로소 집합 알고리즘
런타임 에러
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n + 1)]
def find_parent(x):
if x == parent[x]:
return x
parent[x] = find_parent(parent[x])
return parent[x]
def union_parent(a, b):
a = find_parent(a)
b = find_parent(b)
if a < b:
parent[b] = a
else:
parent[a] = b
for _ in range(m):
k, a, b = map(int, input().split())
if k:
if find_parent(a) == find_parent(b):
print("YES")
else:
print("NO")
else:
union_parent(a, b)
정답
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
parent = [i for i in range(n+1)]
def find(x):
if(parent[x] == x): return x
parent[x] = find(parent[x])
return parent[x]
def union(a,b):
a = find(a)
b = find(b)
if not a == b:
parent[b] = a
def check(a,b):
if find(a) == find(b):
return True
else:
return False
ans = []
for i in range(m):
flag, a, b = map(int,input().split())
if flag == 0 :
union(a,b)
else:
if check(a,b):
ans.append("YES")
else:
ans.append("NO")
for i in range(len(ans)):
print(ans[i])
C++
#include <cstdio>
int p[1000005];
int find(int n){
if (p[n] == n) return n;
return (p[n] = find(p[n]));
}
int uni(int a, int b, int bond){
int c = find(a), d = find(b);
if (c == d) return 1;
if(bond) p[c] = d;
return 0;
}
int main(){
int m, n;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 0, a, b, c; i < m; i++){
scanf("%d%d%d", &a, &b, &c);
if (a == 0)
uni(b, c, 1);
else
printf("%s\n", (uni(b, c, 0)) ? "YES": "NO");
}
}