[백준] 4803번 트리 (C++)

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

 

 

이 문제는 노드 N, 간선 M개가 주어졌을때 간선의 연결관계에 따라서 그래프가 트리인지 판별 후 트리가 될경우
모든 트리의 개수를 구하는 문제이다.

 

여기서 중요한 것은 문제에서 나와있듯이 사이클이 생길 경우 이는 트리가 아니기 때문에

개수로 쳐주지 않는다. 따라서 이 문제는 2가지 방법으로 풀 수 있다.

 

1. 유니온 파인드

만약 유니온 파인드로 풀 경우 먼저 노드 배열을 자기 자신의 노드로 먼저 초기화 해준 뒤 간선에 따라서 같은 부모인지 확인 후

같은 부모가 아닌 경우 root가 낮은얘를 부모로 만들어 합쳐준다 이때 같은 부모인 경우 사이클이 존재하기 때문에 값을 증가시키면 안된다.

 

2. dfs

만약 dfs(깊이 우선 탐색)으로 풀 경우 방문배열을 만들며 방문하지 않았을 경우 현재 노드에서 연결되어 있는 간선을 탐색하여 다음 노드로

넘어갈 수 있는지 확인한다 이때 만약 나를 호출했던 부모와 다음 가야할 노드가 다른 경우 이는 사이클이 존재하는것이기 때문에

개수를 증가시키지 않는다.

 

 

정답 코드(dfs)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N, M;
vector<vector<int>> v(501);
int unf[501];
bool visited[501];
int tmp = 1;

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a > b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b) {
        return true;
    }
    else return false;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

bool dfs(int now, int parent) {
    visited[now] = true;

    for(auto next : v[now]) {
        if(!visited[next]) {
            if(dfs(next, now)) return true;
        }
        else if(parent != next) return true;		// 사이클이 존재하는 경우
    }
    return false;
}

void solve() {
    int cnt = 0;

    for(int i = 1; i <= N; i++) {
        if(!visited[i]) {
            if(!dfs(i, -1)) cnt++;
        }
    }

    if(cnt == 0) {
        cout << "Case " << tmp << ": " << "No trees." << endl;
    }
    else if(cnt > 1) {
        cout << "Case " << tmp << ": " << "A forest of " << cnt << " trees." << endl;
    }
    else {
        cout << "Case " << tmp << ": " << "There is one tree." << endl;
    }
    tmp++;
}

void input() {
    while(true) {
        cin >> N >> M;

        if(N == 0 && M == 0) return;

        v.resize(N+1);

        for(int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }

        solve();
        memset(visited, 0, sizeof(visited));
        v.clear();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}