팀 결성

출처:: 

분류:: union-find

 

1. 문제 이해 및 해결과정

- 서로소 집합 알고리즘 문제, n과 m의 범위가 모두 10,000이상 => 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간복잡도를 개선해야함

 

2. 풀이방법

 1. union-find

#팀 결성
#
import sys
sys.stdin = open("input.txt","r")
#0번 부터 n번까지 팀 존재, m은 연산의 개수
n,m=map(int,input().split())
parent = [0]*(n+1)

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

for i in range(0,n+1):
    parent[i]=i

for _ in range(m):
    c,a,b=map(int,input().split())
    print(parent)
    if c==0:
        union_parent(parent,a,b)
    elif c==1:
        if find_parent(parent,a)==find_parent(parent,b):
            print("YES")
        else:
            print("NO")

3. 오답원인

 

4. 알게된 점