https://www.acmicpc.net/problem/9372
https://github.com/stellaluminary/Baekjoon
본 문제는 최소 신장 트리에 해당하는 문제로 일반적인 크루스칼 알고리즘과 달리 모든 간선의 cost는 1이다.
따라서 이를 고려한 알고리즘을 구현하면 된다.
앞서 cost가 1이라고 말했기 때문에 굳이 edge에 대한 sort과정을 생략하고 cycle인지 아닌지만을 고려한 코드 구현으로 목표를 달성할 수 있다.
import sys
input = sys.stdin.readline
def f_p(p, x):
if p[x] != x:
p[x] = f_p(p, p[x])
return p[x]
def union(p, a, b):
a = f_p(p, a)
b = f_p(p, b)
if a < b:
p[b] = a
else:
p[a] = b
t = int(input())
for i in range(t):
n, m = map(int, input().split())
p = [j for j in range(n+1)]
res = 0
for e in range(m):
a,b = map(int, input().split())
if f_p(p, a) != f_p(p, b):
union(p, a, b)
res += 1
print(res)
최소 신장 트리 혹은 신장 트리를 알고 있다면 굳이 이를 계산할 필요가 있나 생각이 들 것이다. 왜냐하면 모든 국가는 모든 간선의 cost가 1이고 이에 따라 모든 국가를 연결하는 최소 간선의 수는 결국 "모든 국가의 수-1"이 자명하기 때문이다.
이로써 이를 통한 결과를 제출해도 정답이다.
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
n, m = map(int, input().split())
for e in range(m):
a,b = map(int, input().split())
print(n-1)
물론 신장 트리 외 dfs, bfs를 통한 방법 또한 존재한다.
간선의 연결에 대하여 쌍방향의 위치를 넣는 graph list를 생성한다.
그리고 해당 graph를 기반으로 각 node를 방문했는지를 판단하는 visit list를 활용한다.
만약 visit에서 특정 index가 방문했다면 1로 설정하고 방문하지 않았다면 dfs로 재귀를 진행한다.
결과적으로 모든 node의 visit이 1로 방문되었다면 count 값을 반환하여 출력한다.
import sys
input = sys.stdin.readline
def dfs(idx, cnt):
visit[idx] = 1
for i in graph[idx]:
if visit[i] == 0:
cnt = dfs(i, cnt+1)
return cnt
t = int(input())
for _ in range(t):
n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
visit = [0]*(n+1)
cnt = dfs(1, 0)
print(cnt)