4803_트리

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

4803번: 트리

 

 

문제 이해가 살짝 어려웠던 문제이다.

 

먼저 문제 예시를 그림으로 보면서 이해해보자

 

처음 입력케이스는 위와같다. 1,2,3,4 로 이루어진 트리 하나와 5,6의 단독트리가 있음을 알 수 있다.

 

두번째 예시는 위와 같고 하나의 트리로 된것을 알 수 있다.

 

트리 구조는 결국 사이클이 돌지 않아야한다. 즉, 한번 방문했던 노드를 다시 방문하면서 뻗어나가지 않아야 한다는 특징이 있다.

 

만약 위처럼 1-3번 라인이 그어진다고 생각해보자. 1번에서 출발하면 2,3번 노드에 도착하게 되는데 2,3번 노드가 또 서로 이어져 있기때문에 트리구조가 될 수 없는 것이다. 이걸 코드로 구현하면 어떻게 해야할까..

 

바로 1번노드부터 6번노드까지 시작점을 잡은 후, 이어진 간선으로 뻗어나가면서 겹친 점이 있는지 확인하면 된다.

 

이때 이전에 방문했던 점이 없다면 트리구조라고 볼 수 있다. 이러한 방법으로하면 간선이 없는 단점노드여도 인지를할 것이다.

 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(node):
    q = deque([node])
    flag= True
    while q:
        now = q.popleft()
        if visited[now] == 1:
            flag= False
        visited[now] = 1
        for i in graph[now]:
            if not visited[i]:
                q.append(i)
    return flag



case =1
while True:
    n,m = map(int,input().split())
    if n==0 and m ==0:
        break

    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)
    cnt = 0
    for i in range(1,n+1):
        if visited[i] == 1:
            continue
        else:
            if bfs(i):
                cnt +=1
    if cnt == 0:
        print("Case ",case,": No trees.",sep='')
    elif cnt == 1:
        print("Case ",case, ": There is one tree.",sep='')
    else:
        print("Case ",case,": A forest of ",cnt," trees.",sep='')
    case +=1