[백준] 11724-연결 요소의 개수

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

11724번: 연결 요소의 개수

문제 한줄 이해

-노드들이 주어졌을때 이어진 노드들끼리를 한 조라 할때 조의 갯수를 출력하는 문제

 

생각난 풀이

1번째 방법: 방문 체크 리스트를 만들어서 1번 노드부터 방문을 하면서 연결 돼 있는 노드들은 체크를 해나간다.

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
# 노드 갯수 n개 이니깐
graph = [[0 for i in range(n+1)] for i in range(n+1)]
visited = [False]*(n+1)


for i in range(m):
    # 방향이 없는 그래프(무방향 그래프)라는 것은 연결만 된다면 다 갈 수 있다는 뜻
    # 그러면 둘다 1 체크
    x, y = map(int,sys.stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
def bfs(start):
    que = deque()
    que.append(start)
    
    while que:
        nowv = que.popleft()
        
        for i in range(n+1):
            if graph[nowv][i] == 1 and visited[i] == False:
                visited[i] = True
                que.append(i)
    
cnt = 0
for i in range(1,n+1):
# 노드들이 모두 연결이 돼 있다면 탐색에 의해 한번에 visited들이 방문 처리가 되게겠지만
    # 연결이 끊어진 상태라면 bfs()가 여러번 실행이 될테고 그때마다 cnt +=1 을 수행한다.
    if visited[i] == False:
        visited[i] = True
        bfs(i)
        cnt +=1
print(cnt)