그래프 연결요소 - union find로 찾아야하는 연결요소 문제 1 -

1. 문제

 

D - Unicyclic Components (atcoder.jp)

D - Unicyclic Components

 

주어진 그래프에서 모든 연결요소가 정점의 개수와 간선의 개수가 같은지 판단하는 문제

 

2. 풀이

 

연결요소 하니까 BFS로 찾아볼려고 했는데.. 이게 간선을 관리하기가 만만치 않다

 

심지어 이 문제는 두 정점 사이 간선이 여러개 있어도 상관없고, 동일한 정점에 간선이 있는 루프도 있다

 

editorial 피셜로 "One can manage the connectivity of an undirected graph easily with a data structure called Union-Find"

 

방향이 없는 그래프의 연결성을 관리하는 한가지 쉬운 자료구조는 union find

 

---------------------------------------------------------------------------------------------------------------------------------------------

 

rank를 "집합에 포함된 간선의 수"로 정의한다.

 

union만 실수하지 않으면 문제가 없는데

 

1) union 할때마다 간선이 1개 추가되는 거니까 해당 집합에 1이 더해져야 할거고

 

2) 루프가 들어갈 수 있기 때문에 a,b가 서로 같을 수 있다. 

 

이런 경우에 parent를 조절해버리면, parent[a] = a가 되어버려서 초기화 상태로 돌아가 문제가 생긴다

 

그러니까 a,b가 서로 같다면, 간선에 1을 더해 rank만 조절하고 return시킨다

 

3) union시 단순히 rank에 1만 더해지는게 아니고 두 집합 a,b가 union되면, 두 집합 a,b가 가지고 있는 간선이 모두 합쳐져야겠지 

 

def union(a,b,parent):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
 
    if a == b:
        
        rank[a] += 1
        rank[b] = rank[a]
        return
 
    if rank[a] > rank[b]:
        
        parent[b] = a
    
    else:
        
        parent[a] = b
    
    rank[a] += rank[b]
    rank[a] += 1
    rank[b] = rank[a]

 

 

parent, rank를 초기화한 다음에

 

이제 간선을 받을때마다 union을 시키고

 

1번부터 n번까지 순회하여 각 정점의 대표자를 찾는다

 

대표자를 찾을때는 parent값을 찾는게 아니라, find_parent에 넣어야한다는건 이제 기본

 

그리고 해당 대표자가 하나의 연결요소 component를 이룰 것이다. 

 

그래서 그 component에 append시켜준다

 

n,m = map(int,input().split())
 
parent = [i for i in range(n+1)]
rank = [0]*(n+1)
 
for _ in range(m):
    
    u,v = map(int,input().split())
 
    union(u,v,parent)
 
component = [[] for _ in range(n+1)]
 
for i in range(1,n+1):
    
    s = find_parent(i,parent)
 
    component[s].append(i)

 

다시 1번부터 n번까지 순회하여, component가 비어있지 않다면, 

 

해당 집합의 rank는 해당 component의 간선의 수이고, 이것과 component에 들어간 정점의 수가 모두 일치해야한다

 

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x],parent)
    
    return parent[x]
 
def union(a,b,parent):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
 
    if a == b:
        
        rank[a] += 1
        rank[b] = rank[a]
        return
 
    if rank[a] > rank[b]:
        
        parent[b] = a
    
    else:
        
        parent[a] = b
    
    rank[a] += rank[b]
    rank[a] += 1
    rank[b] = rank[a]
 
n,m = map(int,input().split())
 
parent = [i for i in range(n+1)]
rank = [0]*(n+1)
 
for _ in range(m):
    
    u,v = map(int,input().split())
 
    union(u,v,parent)
 
component = [[] for _ in range(n+1)]
 
for i in range(1,n+1):
    
    s = find_parent(i,parent)
 
    component[s].append(i)
 
yes = True
 
for i in range(1,n+1):
    
    a = len(component[i])
    
    if a != 0:
        
        if rank[i] != len(component[i]):
 
            yes = False
            break
 
if yes:
 
    print("Yes")
 
else:
 
    print("No")