그래프 이론, 서로소 집합

" 여러 개의 도시가 연결되어 있다 "

- 노드와 간선으로 이루어진 자료구조, 정점(Vertex)간의 관계를 표현하는 조직도

- 그래프 알고리즘을 의심해보자

- 그래프 자료구조 중에서 Tree 자료구조는 다양한 알고리즘에 사용됨

Tree 자료구조???-
- 부모에서 자식으로 내려오는 계층적인 모델에 속한다.
- Tree 자료구조는 노드가 N개일 때, 항상 간선의 개수가 N -1개 이다.

* 크루스칼 알고리즘 Kruskal - Greedy 알고리즘

(참조)

https://cord-ai.tistory.com/154

Greedy(탐욕)

* 위상 정렬 알고리즘 Topology - Queue or Stack 자료구조를 활용

(참조)

https://cord-ai.tistory.com/156

Stack, Queue, Recursive Function

<크루스칼, 위상 정렬 알고리즘>

https://cord-ai.tistory.com/170

크루스칼, 위상 정렬 알고리즘

 

그래프 VS 트리

	그래프	트리
방향성	방향 그래프 or 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

그래프 구현 방법

- 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식, 우선순위 큐를 이용하는 다익스트라

- 인접 리스트(Adjacency List) : 리스트를 사용하는 방식, 플로이드 워셜 알고리즘

= 메모리와 속도 측면에서 구별되는 특징을 가진다.

(참조)

https://cord-ai.tistory.com/158

DFS / BFS , Graph Structure

 

<기타 그래프 알고리즘>

- 서로소 집합

- 신장 트리, 크루스칼 알고리즘

- 위상 정렬

 

서로소 집합

" 공통 원소가 없는 두 집합 "

- 트리 자료구조를 이용하여 집합을 표현

* {1, 2}, {3, 4}는 서로소 관계이다

* {1, 2}, {2, 3}는 서로소 관계까 아니다.

서로소 집합 자료구조란,  union-find 자료구조라고도 불림???
- 서로서 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- union(합집합) 연산, find(찾기) 연산

<트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘>
1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
- A와 B의 루트 노드 A', B'를 각각 찾는다.
= 실제로 구현할 때는 A'와 B' 중에서 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많음
= A' = 1, B' = 3이라면 B' 가 A'를 가리키도록 설정(가리키다 = 부모 노드로 설정)
= B'가 A'를 부모 노드로 설정하는 것을 그래프로 시각화할 때, B'와 A'를 간선으로 연결하는 형태로 그래프를 그릴 수 있다.

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복

<예시>

{1, 2, 3, 4, 5, 6}, 6개의 원소(=노드)로 구성되어 있는 상황에 아래와 같은 4개의 union 연산(=간선)이 존재한다고 가정

- union 1, 4, '1과 4는 같은 집합'

- union 2, 3, '2과 3는 같은 집합'

- union 2, 4, ....

- union 5, 6, ....

이러한 union 연산들은 그래프 형태로 표현될 수도 있다. 원소는 그래프에서의 노드로 표현되고
'같은 집합에 속한다'는 정보를 담은 union 연산들은 간선으로 표현된다.

일반적으로 서로소 집합을 그림으로 표현할 때는 번호가 큰 노드 ->번호가 작은 노드를 간선으로 가리키도록 트리 구조를 이용해 그림을 그리게 된다. 즉, 트리 구조상 번호가 작은 노드가 부모가 되고, 번호가 큰 노드가 자식이 된다.

 

노드 간의 관계 / 서로 다른 집합

- 전체 원소가 {1, 2, 3, 4}와 {5, 6}이라는 두 집합으로 나누어지는 것을 알 수 있다(= 같은 집합에 속한다)

- 노드 3의 부모 노드 = 노드 2 / 다만, 노드 2의 부모 노든 = 1이기 때문에 최종적으로 노드 3의 루트 노드는 1이라고 볼 수 있다.

## 각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 구현

'''
가장 먼저 노드의 개수(V) 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을
부모로 가지도록 설정한다. 현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재

<유의할점>
부모 테이블은 말 그대로 부모에 대한 정보만을 담고 있다. 다시말해 특정한 노드의 부모에 대해서만 저장
실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야 한다.
6 4
1 4
2 3
2 4
5 6
'''

import sys

input = sys.stdin.readline

v, e = map(int, input().split())

# 부모 테이블 초기화
# + 1을 해주는 이유는 노드 번호가 첫 번째로 시작하기 때문에 이후 출력시 이해하기 쉽게 하기위함
parent = [0] * (v + 1)

# 특정 원소가 속한 집합 찾기 / 같은 루트 노드를 가지는 것이 있을 경우 한 번더 확인
def find_parent(parent, x):

    # 루트 노드가 아니라면, 루트 노드를 찾을때까지 재귀
    if parent[x] != x:
        return find_parent(parent, parent[x])
    
    return x

## 경로 압축 Path Compression
'''
위와 같은 find함수의 경우는 비효율적으로 동작
<예시>
(4, 5), (3, 4), (2, 3), (1, 2)와 같이 주어졌을 때 노드 5의 루트를 찾기 위해서는
노드 5 -> 노드 4 -> 노드 3-> 노드 2-> 노드 1 순서대로 부모 노드를 거슬러 올라가야하므로 최대 O(V) 시간 소요
노드의 개수가 V, find(), union() 연산의 개수가 M개일 때, 전체 시간 복잡도 O(VM)
= So, 부모 테이블값을 갱신함으로써 루트 노드에 더 빠르게 접근할 수 있다.
'''
def find_parent_com(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_com(parent, a)
    b = find_parent_com(parent, b)

    if a < b:
        parent[b] = a

    else:
        parent[a] = b


# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

for i in range(e):
    a, b = map(int, input().split())
    
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent_com(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
for i in range(1, v+1):
    print(parent[i], end=" ")

<경로 압축 방법>

- 노드의 개수 V, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축방법을 적용한 시간 복잡도는 $$O(V + M(1 + log_{2-M/V}V))$$

 

서로소 집합을 활용한 사이클 판별

- 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다.

- 무방향 그래프에서만 적용 가능

- 방향 그래프에선 DFS를 이용하여 판별할 수 있음(= 해당 내용 다루지 않음)

 

union 연산은 그래프에서의 간선으로 표현될 수 있고 따라서 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인, find 함수 적용
- 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행
- 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것

2. 그래프에서 포함되어 있는 모든 간선에 대하여 1번 과정 반복

" 두 노드를 확인시 해당 노드의 부모 노드가 둘다 1이면 이미 같은 집합에 속해있다고 볼 수 있다. "

----- 생략 -----
'''
3 3
1 2
1 3
2 3
'''

# 사이클 여부
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
    
    # 사이클 발생하지 않는다면 union연산 수행
    union_parent(parent, a, b)
    
    
## 사이클 여부
if cycle:
    print("사이클 발생")

else:
    print("사이클 발생 X")