BOJ 20955 민서의 응급 수술

https://www.acmicpc.net/problem/20955
시간 1초, 메모리 1024MB

input :

• N, M (2 ≤ N ≤ 100,000, 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000))
• 연결된 뉴런의 번호 u, v (1 ≤ u, v ≤ N, u ≠ v)

output :

• 모든 뉴런을 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 출력

조건 :

• 연결되지 않은 두 뉴런을 연결

• 이미 연결된 두 뉴런의 연결을 끊는다.

---

2가지 방법을 사용할 수 있다. union - find를 사용하거나, bfs를 통해 연결을 시키는 방식이다.

어차피 정답을 구할 때는 (연결되어 있는 부분 트리 - 1) + (사이클 때문에 끊어야 하는 간선[모든 간선 - 실제 사용 간선]) 이라고 볼 수 있다.

그리고 간선을 입력 받았을 때, 단방향으로 이 간선을 저장하게 되면 순서에 의해 연결되어 있는 부분트리의 개수가 씹힐 수도 있기에 양방향으로 체킹을 해야 한다.

import sys
from sys import setrecursionlimit
setrecursionlimit(100000)

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

def union(a, b):
    parent_a = find(a)
    parent_b = find(b)

    if parent_a > parent_b:
        parent[parent_a] = parent_b
    else:
        parent[parent_b] = parent_a

n, m = map(int, sys.stdin.readline().split())
parent, cycle = [i for i in range(n + 1)], 0

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())

    if find(u) == find(v):
        cycle += 1
    else:
        union(u, v)

edge = 0
for i in range(1, n):
    if find(i) == find(i + 1):
        continue
    union(i, i + 1)
    edge += 1

print(cycle + edge)

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph, visit = dict(), [0] * (n + 1)

for i in range(1, n + 1):
    graph[i] = []
    
for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
    
cnt, using = 0, 0
for i in range(1, n + 1):
    if not visit[i]:
        cnt += 1
        
        visit[i] = 1
        q = deque([i])
        while q:
            node = q.popleft()
            
            for next_node in graph[node]:
                if not visit[next_node]:
                    visit[next_node] = 1
                    q.append(next_node)
                    using += 1
                    
print(cnt - 1 + m - using)