[BOJ/백준][Gold4] 4803 : 트리 (C++)

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

4803번: 트리

 

[난이도] Gold4
[유형] DFS

[풀이]
DFS를 이용해서 cycle이 없는 연결요소를 찾아야 한다.
cycle을 찾는 방법은 다음과 같다.
1. DFS로 방문하는 순서를 dfs(int n,int cnt)와 같이 cnt를 한개씩 증가시키면 visit 배열에
기록해준다.
2. 인접한 노드가 cnt보다 2이상 큰수라면 이미 방문한 노드이므로 cycle이 있는것이다. (1이면 부모노드이므로 skip)
=> cycle이 없는 연결요소들의 개수가 정답이다.

 

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[501],tc;
vector<int> adj[501];
bool ok =1;
void dfs(int n,int cnt){
    visit[n]=cnt;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,cnt+1);
        else if(visit[n]-visit[nxt]>1) ok=0;
    }
}
int main(){
    while(1){
        scanf("%d%d",&N,&M);
        memset(visit,0,sizeof(visit));
        for(int i=0;i<=N;i++) adj[i].clear();
        if(N==0) break;
        while(M--){
            int u,v;
            scanf("%d%d",&u,&v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int ans = 0;
        for(int i=1;i<=N;i++){
            if(!visit[i]){
                ok=1;
                dfs(i,0);
                ans+=ok;
            }
        }
        printf("Case %d: ",++tc);
        if(ans==0) puts("No trees.");
        else if(ans==1) puts("There is one tree.");
        else printf("A forest of %d trees.\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/4803.cpp