[백준/dfs] 4803번: 트리

-문제:https://www.acmicpc.net/problem/4803

 

주어진 트리에서 연결요소의 갯수를 구하고, 사이클이 있는지 여부를 확인하는 것이다. 

그렇게 어렵지 않아 여러번 시도했지만 계속 16%에서 틀려서 구글링했다

내가 작성한 코드를 파이썬 튜터를 돌리니 3개의 트리가 나와야하는데 계속 4개가 나온다. 문제점을 찾고, 정답 코드를 한번 스스로 작성해볼것이다

 

-정답풀이: 

그리고 Case{1}: 꼭 붙여서 작성하기!!

import sys
input=sys.stdin.readline

def dfs(prev,v):
    visit[v]=1
    for i in graph[v]:
        if i==prev:
            continue
        if visit[i]:
            return False
        if not dfs(v,i):
            return False
    return True

tc=0
while True:
    tc+=1
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    graph=[[] for _ in range(n+1)]
    visit=[0]*(n+1)
    for _ in range(m):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    cnt=0
    for i in range(1,n+1):
        if not visit[i]:
            if dfs(0,i):
                cnt+=1
    if cnt==0:
        print('Case {}: No trees.'.format(tc))
    elif cnt==1:
        print('Case {}: There is one tree.'.format(tc))
    else:
        print('Case {}: A forest of {} trees.'.format(tc,cnt))