183. 집합의 표현

아현·2021년 7월 12일
0

Algorithm

목록 보기
188/400
post-custom-banner

백준




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");
  }

}

profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글