서로소 집합을 활용한 사이클 판별(같은 팀인지 파악)

1. 각 edge를 확인하며 두 node의 root node를 확인
    - root node가 서로 다르다면 두 노드에 대해 union 연산 수행
    - root node가 서로 같다면 cycle이 발생한 것임 (같은 팀임)
2. 그래프에 포함된 모든 edge에 대해 반복

 

입력 첫째줄에 노드의 개수, 간선(edge)의 개수 입력받기

cycle 생성 여부 출력하기

예제 입력	예제 출력
3 3 1 2 1 3 2 3	사이클 없음

def find_parent(parent, x): # 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 # 1과 2가 연결되어 있으면 parent[2] = 1
    else:
        parent[a] = b



v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
for i in range(1, v+1): # 부모 테이블 자기 자신으로 설정
    parent[i] = i
cycle = False
for i in range(e):
    a,b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클 있음")
else:
    print("사이클 없음")

---

예제 : 팀 결성

문제

 

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.

1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

• 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 <= N, M <= 100,000)
• 다음 M개의 줄에는 각각의 연산이 주어진다.
• '팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
• '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
• a와 b는 N 이하의 양의 정수이다.
• '같은 팀 여부 확인'연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

 

예제 입력	예제 출력
7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1	NO NO YES

 

 

풀이

1. parent list를 만들어둬서 같은 그룹에 있는 지 확인할 수 있도록 하자

2. find_parent , union_parent 두 개의 함수를 사용하자

def find_parent(parent, x): # 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 # 1과 2가 연결되어 있으면 parent[2] = 1
    else:
        parent[a] = b


n, m = map(int, input().split())
parent = [0] * (n+1) # 부모 테이블 초기화
for i in range(1, n+1): # 부모 테이블 자기 자신으로 설정
    parent[i] = i
ans = False
for i in range(m):
    oper, a, b = map(int, input().split())
    if oper == 0: # 팀 합치기
        union_parent(parent, a, b)
    else: # 확인
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")