code review/bfs-dfs

[python] 백준 11724번 : 연결 요소의 개수 (BFS, union&find)

jmHan 2022. 2. 25. 16:35
반응형

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

 

11724번: 연결 요소의 개수

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

www.acmicpc.net

 

 

1. union find로 구현 

# 정점, 간선의 개수
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
parent = [i for i in range(n+1)]

def find(x, parent):
    if parent[x] != x:
        return find(parent[x], parent)
    return x

def union(a, b, parent):
    a = find(a, parent)
    b = find(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for a in range(1, n+1):
    for b in graph[a]:
        # 그룹 만들기
        union(a, b, parent)
        
# 속한 집합의 루트노드 카운트
result = set()
for i in range(1, n+1):
    result.add(parent[i])
print(len(result))

2. bfs 구현 

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
result = 0

def bfs(x):
    que = deque([x])
    visited[x] = True
    while que:
        now = que.popleft()
        for _next in graph[now]:
            if not visited[_next]:
                que.append(_next)
                visited[_next] = True
    return 1

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    if not visited[i]:
        result += bfs(i)
print(result)
반응형