[백준] 11724번 연결 요소의 개수 [Python] - 그래프 이론

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

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

 

1번 노드부터 시작해서 연결된 번호의 노드를 훑고 지나면서

각 노드랑 연결된 노드까지도 살펴봅니다.

방문한 노드는 기록하고 이후부터는 방문하지 않은 노드에 대해 위 과정을 거칩니다.

각 과정을 거칠 때마다 숫자를 세서 연결 요소의 개수를 구합니다. 

import sys

# 방문하지 않은 노드를 찾아서 연결된 노드를 훑으며 방문 기록을 남기는 함수
# 각 연결된 노드들의 방문이 하나의 연결 요소이므로 개수를 셈 
def f(N, G, V):
    c = 0
    for n in range(1,N+1):
        if not V[n]:
            c += 1
            V[n] = True
            li = [n]
            while li:
                s = li.pop(0)
                for t in G[s]:
                    if not V[t]:
                        V[t] = True
                        li.append(t)
    print(c)

# 연결 관계를 나타내는 2차원 리스트 생성 함수
def g(N, M):
    G = [[] for _ in range(N+1)]
    V = [False] * (N+1)
    for _ in range(M):
        i, j = map(int, sys.stdin.readline().split())
        G[i].append(j)
        G[j].append(i)
    f(N, G, V)

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    g(N, M)

 

각 노드의 연결 상태를 대표할 리스트를 생성하고

연결된 노드의 번호들의 인덱스에 같은 값을 저장, 업데이트함

 

연결 요소의 개수를 처음에 N$($노드의 수$)$개로 세팅하고

새로운 연결이 확인 될 때마다 -1을 합니다.

import sys
def f(N, M):
    c, t = N, 1
    li = [0 for _ in range(N+1)]
    for _ in range(M):
        if c == 1: break
        i, j = map(int, sys.stdin.readline().split())
        if li[i] * li[j] == 0:
            if li[i] == li[j]:
                li[i] = li[j] = t
                t += 1
            else:
                li[i] = li[j] = li[i]+li[j]
        elif li[i] != li[j]:
            s = min(li[i], li[j])
            l = max(li[i], li[j])
            for k in range(1, N+1):
                if li[k] == l:
                    li[k] = s
        else: c += 1
        c -= 1
    print(c)

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    f(N, M)

 

예제 입력 1 

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 

2

예제 입력 2 

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 

1