입력으로 그래프가 주어집니다. 이 그래프는 연결 그래프가 아닐 수 있습니다. 다시 말해서, 여러 개의 연결 요소로 이루어져 있을 수 있습니다.
여기서 연결 요소는
(1) 모든 정점이 서로 연결되어 있는 정점의 부분집합이며
(2) 이 연결 요소에 포함되는 정점들은 외부 정점들과 연결되어서는 안됩니다.
트리는 다음 조건을 만족하는 연결 요소입니다. 셋 중 하나만 만족해도 나머지를 만족하게 됩니다.
사이클이 없습니다.
정점이 n개이면, 간선이 n - 1개 있습니다
임의의 두 정점에 대해서 경로가 유일합니다.
이 그래프상의 연결 요소 중, 트리에 해당하는 것의 개수를 세는 프로그램을 작성해보세요.
--> 즉 사이클이 없는 노드의 연결들을 하나로 카운트하는 트리의 개수 구하기 문제
입력 형식
첫 번째 줄에는 정점의 개수 n, 간선의 개수 m이 주어집니다.
두 번째 줄부터 m+1 번째 줄에 각각 걸쳐 간선으로 연결된 두 개의 노드가 공백을 두고 차례대로 주어집니다. 주어지는 노드의 번호는 1에서 n 사이입니다.
2 ≤ n ≤ 500
1 ≤ m ≤ n(n-1)/2
출력형식
주어진 그래프의 연결 요소 중 트리인 것의 개수를 출력합니다.
예제1
입력:
6 3 1 2 2 3 3 4
출력:
3
-> 설명
노드가 6번까지 있음, 1-2-3-4로 하나 연결 되어 있고, 5, 6 이렇게 3개가 Tree
예제2
입력:
6 5 1 2 2 3 3 4 4 5 5 6
출력:
1
예제3
입력:
6 6 1 2 2 3 1 3 4 5 5 6 6 4
출력:
0
BFS, DFS, 유니온 파인드, 그래프, 트리 문제이다.
1. BFS로 푸는 법
import sys
from collections import deque
def BFS(x):
isTree = True
Q=deque()
Q.append(x)
while Q:
now = Q.popleft()
if visited[now]==1: # 연결된 노드를 타고 가다 이미 방문한적 있는 노드에 도달하면
isTree=False # 그건 사이클이라는 뜻 -> 트리 아님
visited[now]=1
for e in graph[now]:
if visited[e]==0:
Q.append(e)
return isTree
if __name__=="__main__":
n,m=map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a,b=map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0]*(n+1)
treeCnt=0
for i in range(1,n+1):
if visited[i]==1:
continue
if BFS(i) is True:
treeCnt += 1
print(treeCnt)
2. DFS로 푸는법
import sys
sys.stdin=open('input.txt', 'r')
# dfs 탐색을 진행합니다.
def DFS(x):
global vcnt, ecnt
for y in graph[x]:
# 간선 개수를 세어줍니다.
ecnt += 1
# 이미 방문한 정점이면 스킵합니다.
if visited[y]:
continue
visited[y] = True
vcnt += 1 # 정점 개수를 세어줍니다.
DFS(y)
if __name__=="__main__":
n,m=map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
for _ in range(m):
a,b=map(int, input().split())
graph[a].append(b)
graph[b].append(a)
ans = 0
vcnt = 0
ecnt = 0
# 모든 정점을 방문해 트리 여부를 탐색합니다.
for i in range(1, n + 1):
if visited[i]:
continue
visited[i] = True
vcnt = 1
ecnt = 0
DFS(i)
# 2번씩 중복 세어진 경우를 처리합니다.
ecnt = ecnt // 2
# 트리의 성질을 만족한다면
# 답을 갱신해줍니다.
if vcnt - 1 == ecnt:
ans += 1
# 컴퍼넌트 중 트리인 것의 개수를 출력합니다.
print(ans)
각 연결 요소에 대해 DFS 탐색을 진행하여 정점의 개수 -1이 간선의 개수가 되는지 확인합니다.
여러 개의 연결 요소로 이루어진 문제이므로 각 연결 요소에 대해 DFS 탐색을 진행합니다. 탐색 이후의 결과가
'정점의 개수 - 1 = 간선의 개수'를 만족한다면 이는 트리가 됩니다. 따라서 해당 조건을 만족하는 경우를 전부 세어주면 됩니다. n개의 노드와 m개의 간선으로 이루어진 그래프가 주어지므로 총 시간복잡도는 O(N+M)이 됩니다.
3. 유니온 파인드로 푸는 방법
import sys
def union(x,y):
x = find(x)
y = find(y)
if x < y:
parents[y] = x
else:
parents[x] = y
def find(x):
if x != parents[x]:
parents[x] = find(parents[x])
return parents[x]
if __name__=="__main__":
n,m=map(int, input().split())
parents = [i for i in range(n+1)]
cycle = set()
for _ in range(m):
a,b = map(int,input().split())
if find(a) == find(b):
cycle.add(parents[a])
cycle.add(parents[b])
# 두 정점 중 하나가 사이클에 포함되는 정점이라면 나머지 정점도 사이클로 포함한다.
if parents[a] in cycle or parents[b] in cycle:
cycle.add(parents[a])
cycle.add(parents[b])
union(a,b)
for i in range(n+1):
find(i)
parents = set(parents)
ans = sum([1 if i not in cycle else 0 for i in parents])-1
print(ans)
