[백준 4803번] [트리 / 사이클 존재 여부] 트리

Approach

트리의 개수는 전체 component 개수에서 사이클을 가지는 component 개수를 제외해주면 된다.

 

Component 개수를 구하는 것은 dfs를 호출하는 횟수와 동일하므로, 사이클이 발생하는지 여부만 체크해주면 된다.

앞에서 풀었던 문제들과 달리 한 정점에서 반드시 사이클을 지시하고 있지는 않은 상황이므로(https://viyoung.tistory.com/327)

[백준 10265번] [DFS / SCC] MT

무작정 사이클이 나타날때까지 계속해서 visited 배열을 초기화하면서 dfs를 돌릴수도 없는 노릇이다. (DFS로 component에 속한 모든 edge를 탐색하려면 indegree가 1이상 보장되어야한다. 만약 non directional로 잡을 경우 무조건 사이클로 잡히게 되는 문제가 존재하게 된다.)

 

이 지점을 유니온 파인드로 해결할 수는 있다. dfs를 통해 방문했던 지점을 방문하려고 했을 때, 방문 전 정점과 방문 후 정점이 같은 분리집합 안에 속해있을 경우에는 사이클이 아니지만, 다른 분리 집합에 속한 경우에는 사이클이게 되기 때문이다.

 

더 쉬운 방법으로는 non-directional로 주어진 간선을 넣게 되면, 기존의 간선들이 2개로 분리가 된다.

따라서 무조건 component에 속한 모든 정점이 indegree가 1이상이므로 DFS를 통해 탐색가능하다. 따라서 DFS를 통해 탐색을 해나가는 과정에서 간선이 존재하면 체크해두고, 그 값은 2로 나누면 해당 component 안에 속한 간선의 수와 같다.

해당 값이 정점의 개수 - 1이면 트리이고, 그렇지 않으면 사이클이 존재하게 된다. 

 

쉽게 해당 그래프에서 사이클이 존재하는지 여부를 판단할 수 있는 아이디어이므로 잘 알아두도록 하자.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
bool visited[501];
vector<vector<int> > r;

int edge_count;
int dfs(int x){
    visited[x] = 1;
    int comp_num = 0;
    for(int i = 0; i < r[x].size(); i++){
        edge_count++;
        int cur = r[x][i];
        if(!visited[cur]){
            comp_num += dfs(cur);
        }
    }
    return comp_num + 1;
}

int main(void){
    fastio;
    int case_num = 1;
    while(true){
        memset(visited, 0, sizeof(visited));
        int n, m;
        cin >> n >> m;
        if(n == 0 && m == 0) return 0;

        r = vector<vector<int> > (n + 1);

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

        int tree_num = 0;

        for(int i = 1; i <= n; i++){
            if(!visited[i]){
                edge_count = 0;
                int node_count = dfs(i);
                if(edge_count / 2 == node_count - 1) tree_num++;
            }
        }

        if(tree_num == 0){
            cout << "Case " << case_num << ": No trees.\n";
        }
        else if(tree_num == 1){
            cout << "Case " << case_num << ": There is one tree.\n";

        }
        else{
            cout << "Case " << case_num << ": A forest of " << tree_num << " trees.\n";

        }
        case_num++;
    }

}