파이썬 백준 1717번 : 집합의 표현

문제

https://www.acmicpc.net/problem/1717

 

 

풀이

크루스칼 알고리즘의 find_set, union을 이용해서 풀었다.

부모가 같으면 같은 집합에 해당한다.

 

import sys

sys.setrecursionlimit(1000000)

n, m = map(int, sys.stdin.readline().split())
parent = [i for i in range(n + 1)]  # 부모집합 초기화 (처음엔 자기 자신을 부모로 가짐)

def find_set(x): #부모 찾기 
    if parent[x] != x:
        parent[x] = find_set(parent[x])
    return parent[x]

def union(a, b): # union -> 그룹 합치기
    a = find_set(a)
    b = find_set(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


for _ in range(m):
    operation, a, b = map(int, sys.stdin.readline().split())
    if operation == 0: #합집합 연산
        union(a, b)
    else: #1이면 같은 집합 인지 확인
        if find_set(a) == find_set(b): #부모가 같으면 같은 집합 내에 있음
            print("YES")
        else:
            print("NO")

 

 

 

 

 

 

 

덧)

처음에 집합 연산으로 푸니 메모리 초과가 발생했다.. 

import sys

n,m=map(int,sys.stdin.readline().split())
set_list=[]
for i in range(n+1) :
    temp=set()
    temp.add(i)
    set_list.append(temp)
#print(set_list)

for _ in range(m):
    operation,a,b=map(int,sys.stdin.readline().split())
    if operation == 0:
        target1=target2=None
        for sets in set_list:
            if a in sets:
                target1=sets
            if b in sets:
                target2=sets

        #print(target1,target2)
        if target1 in set_list:
            set_list.remove(target1)
        if target2 in set_list:
            set_list.remove(target2)
        temp_set=set(target1|target2)
        set_list.append(temp_set)
        #print(set_list)
    else:
        cnt=0
        for sets in set_list:
            if a in sets and b in sets:
                print("YES")
                cnt=1
                break
        if cnt==0:
            print("NO")