11724 - 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

 

- 그래프 탐색

 

import sys
input = sys.stdin.readline

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.visited = [False] * size
    
    def addEdge(self, u, v):
        self.matrix[u][v] = self.matrix[v][u] = 1

    def printGraph(self):
        for i in self.matrix:
            print(*i)

    def dfs(self, k):
        self.visited[k] = True
        for i in range(self.size):
            if self.visited[i] == False and self.matrix[k][i] == 1:
                self.dfs(i)
    
    def returnVisited(self):
        return self.visited

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

g = Graph(n)
for _ in range(m):
    e1, e2 = map(int, input().split())
    g.addEdge(e1-1, e2-1)

cnt = 0
for i in range(n):
    if g.returnVisited()[i] == False:
        g.dfs(i)
        cnt += 1

print(cnt)

 

연결 요소가 뭔지 몰라서 검색했다

연결되지 않은 그래프의 개수를 연결 요소의 개수라고 하더라!

 

아이디어는 간단하게 visited 리스트 선언해서, False인 것만 탐색 돌리고 탐색에서 나온 곳은 True로 변경해주면 된다

 

바로 품ㅎ