ABC 293 복기 - D Tying Rope - 그래프 연결요소, cycle 판단 -

1. 연결요소

 

연결 요소(Connected Component) (velog.io)

연결 요소(Connected Component)

 

 

 

위 그래프가 2개의 그래프로 볼 수도 있지만, 1개의 그래프가 2개의 연결요소를 가진다고 볼 수 있다.

 

연결요소(connected component)는 해당 요소에 속하는 모든 정점을 연결하는 경로가 있어야하고

 

또 다른 연결요소에 속한 정점과 연결하는 경로가 없어야한다.

 

 

2. 문제

 

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

 

BFS를 이용해서 간단하게 찾을 수 있다

 

1번부터 N번 정점까지 순회해서 이미 방문했던 정점은 넘기고 방문하지 않은 정점은 BFS 탐색을 시도해서

 

큐가 비면 True를 return하도록 한다

 

True를 return한 순간 count에 1을 더해준다

 

from collections import deque
from sys import stdin

def bfs(x,n,visited,graph):
    
    queue = deque([x])

    visited[x] = 1

    while queue:
        
        x = queue.popleft()

        for v in graph[x]:
            
            if visited[v] == 0:
                
                visited[v] = 1
                queue.append(v)
    
    return True


n,m = map(int,stdin.readline().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    graph[u].append(v)
    graph[v].append(u)

visited = [0]*(n+1)

count = 0

for i in range(1,n+1):
    
    if visited[i] == 0:
        
        count += bfs(i,n,visited,graph)

print(count)

 

 

3. D - Tying Rope

 

D - Tying Rope (atcoder.jp)

D - Tying Rope

 

문제를 잘 보면 N개의 로프가 있는데, 1번부터 N번까지 번호가 있다

 

한쪽이 빨간색으로 칠해져있으면, 다른 쪽은 파란색으로 칠해져있다

 

로프를 묶는 M개의 연산이 주어진다.

 

i번째 연산은, $A_{i}$의 $B_{i}$로 칠해진 부분을 $C_{i}$의 $D_{i}$로 칠해진 부분과 묶는 것이다.

 

이 때 동일한 색을 여러번 묶지는 않는다. 하나의 색은 1번만 묶는데 사용할 수 있다.

 

모든 연산이 끝난 후에, 사이클이 되는 그룹의 수와 그렇지 않는 그룹의 수를 구해라

 

 

4. official editorial 풀이

 

이 문제는 다음과 같이 바꿔 쓸 수 있다.

 

"N개의 정점이 있고 M개의 간선이 주어진다. i번째 간선은 $A_{i}$와 $C_{i}$를 연결하는 간선이다.

 

간선이 빨간색, 파란색 양끝에서만 연결 될 수 있으므로, 모든 정점은 최대 2개의 연결차수를 가진다.  

 

이 때, 사이클이 있는 연결요소의 개수와 사이클이 없는 연결요소의 개수를 구해라"

 

문제를 바꿔쓸수 있다는게 놀랍네

 

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

 

***연결요소가 사이클을 가질 필요충분조건

 

연결요소가 사이클을 가질 필요충분조건은, 연결요소의 모든 정점이 연결차수가 2여야한다.

 

따라서 모든 정점의 연결차수도 같이 저장하면서 BFS를 통해 사이클이 존재하는 연결요소인지 판단해보면 되겠다.

 

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

 

그래프의 연결차수는 BFS를 돌면서 구하는게 아니라,

 

입력을 받을 때 구하면 된다

 

연결차수를 미리 구해놓는게 핵심

 

from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

visited = [0]*(n+1)
degree = [0]*(n+1)

#그래프를 만들때, 연결차수도 구해준다.
for _ in range(m):
    
    a,b,c,d = input().split()

    a = int(a)
    c = int(c)
    
    graph[a].append(c)
    graph[c].append(a)

    degree[a] += 1
    degree[c] += 1

 

 

다음으로 1번부터 N번까지 순회하면서 각 정점부터 시작해서 BFS를 수행한다.

 

방문하는 정점의 연결차수가 2가 아니라면, 애초에 해당 정점을 포함하는 연결요소는 사이클이 존재할 수가 없다.

 

처음에 flag = True로 두고, 방문하는 정점의 연결차수가 2가 아니면 flag = False로 바꾸고 

 

해당 정점에 대한 BFS 수행이 끝나면, flag에 따라 cycle값에 1을 더해주거나 no_cycle에 1을 더해주거나

 

from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

visited = [0]*(n+1)
degree = [0]*(n+1)

#그래프를 만들때, 연결차수도 구해준다.
for _ in range(m):
    
    a,b,c,d = input().split()

    a = int(a)
    c = int(c)
    
    graph[a].append(c)
    graph[c].append(a)

    degree[a] += 1
    degree[c] += 1

#1번부터 N번까지 BFS수행
cycle = 0
no_cycle = 0

for i in range(1,n+1):
    
    if visited[i] == 0:
        
        queue = deque([i])

        visited[i] = 1
         
        flag = True #연결요소의 cycle이 존재한다.

        while queue:
            
            x = queue.popleft()
            
            #방문한 정점이 연결차수가 2가 아니라면,
            #해당 정점을 포함하는 연결요소는 사이클이 없다
            if degree[x] != 2:
                
                flag = False
            
            for v in graph[x]:
                
                if visited[v] == 0:
                    
                    queue.append(v)
                    visited[v] = 1
        
        #정점 i를 포함하는 연결요소를 만들고 나서, flag=True라면
        #해당 연결요소의 모든 정점은 연결차수가 2이다.
        #그래서 사이클이 존재함
        if flag == True:
            
            cycle += 1
        
        else:
            
            no_cycle += 1

print(cycle, no_cycle)