[백준] 11724. 연결 요소의 개수 (+파이썬 코드)

Question. 백준 11724. 연결 요소의 개수

 

 

 

---

Answer.

 

프로그래머스의 "네트워크"랑 비슷한 문제여서 자세한 풀이는 생략한다.

sohyunwriter.tistory.com/90

[프로그래머스] "네트워크" (+파이썬 코드)

 

sol 1) 인접리스트 + dfs 반복문

 

주의사항

1) sys.stdin.readline 써야 시간초과 안 남

2) dfs 돌릴 때, visited한 node는 continue 해야 시간초과 안 남

 

import sys
input = sys.stdin.readline

def count_connected_component(n, graph):
    cnt = 0
    visited = [False] * (n+1)

    def dfs(graph, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j]:
                continue

            visited[j] = True

            for i in graph[j]:
                if not visited[i]:
                    stack.append(i)

    for i in range(1, n+1):
        if not visited[i]:
            dfs(graph, visited, i)
            cnt += 1
    return cnt

if __name__ == "__main__":
    n, m = map(int, input().split())

    # make graph
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # count connected component
    answer = count_connected_component(n, graph)

    print(answer)

 

 

sol 1)
Time Complexity	O(V+E)
Space Complexity	O(V+E)