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

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

11724번: 연결 요소의 개수

 

 

# 조건

• 방향 없는 그래프가 주어질 때, 연결 요소의 개수를 구하라
• 1<=N<=1000, 0<=M<=Nx(N-1)/2

 

# 접근 방법

• 연결 요소란 사이클이 존재하는 그래프를 말하는 것 같다.
• 따라서 시작위치부터 한 바퀴를 돌며 방문한 정점을 체크해주고, +1
• 이후 방문하지 않은 곳에서 시작하여 위의 과정 반복해준다.

 

 

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
def bfs(n):  
    q = deque()  
    q.append(n)  
    while q:  
        start = q.popleft()  
        for j in range(1, N+1):  
            # 방문하지 않았다면  
            if graph[start][j] and visited[j] == 0:  
                q.append(j)  
                visited[j] = 1  
    return visited  
  
  
N, M = map(int, input().split())  
  
# 전체 정점 리스트  
graph = [[0]*(N+1) for _ in range(N+1)]  
  
# 간선 정보 받아주며 기록하기  
for _ in range(M):  
    a, b = map(int, input().split())  
    graph[a][b] = 1  
    graph[b][a] = 1  
  
# 방문 기록  
visited = [0] * (N+1)  
# 결과  
result = 0  
for i in range(1, N+1):  
    if visited[i] == 0:  
        bfs(i)  
        result += 1  
  
print(result)