백준 4803 - 트리

문제 설명

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 그래프에서 트리가 몇 개인지 구하면 된다.

 

해당 문제는 사이클 판정이 핵심이다.

일반적인 사이클 판정은 dfs를 통해 알아낼 수 있다.

연결된 노드를 순회하며 이미 방문한 노드에 다시 방문한다면 사이클이 존재하는 것이다.

bool Dfs(int start, int prev)
{
    visited[start] = true;
    for (auto node : graph[start])
    {
        if (node == prev) continue;

        if (visited[node]) return false;
        if (!Dfs(node, start)) return false;
    }

    return true;
}

 

이를 통해 사이클이 있는 노드들을 제외한 나머지 노드들의 개수를 세면 된다.

int cnt = 0;
for (int i = 1; i <= N; i++)
{
    if (visited[i]) continue;
    if (Dfs(i, 0)) cnt++;
}

 

처음에는 Union-Find를 통해 루트개수만 세면 된다고 생각했다.

근데 사이클 판정을 어떻게 해야 할지 모르겠어서 DFS로 전환하였는데 Union-Find로도 충분히 풀 수 있다고 하여 기록한다.

Union-Find에서 사이클 판정은 같은 부모를 갖는 노드를 연결한다면 사이클이 존재한다고 판정할 수 있다.

따라서, 두 노드의 부모가 같은 노드가 생긴다면 해당 노드의 parent를 유효하지 않은 값으로 변경하고 모든 간선을 처리한다면 트리가 이루어진 노드는 자기 자신을 parent로 갖는 노드가 반드시 1개 존재한다.

즉, 모든 간선을 처리한 후 모든 노드의 parent를 돌며 자기 자신인 개수를 세면 트리의 개수를 알 수 있다.

int Find(int x)
{
    if (x == parent[x]) return x;
    return parent[x] = Find(parent[x]);
}

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

    if (a == b)
    {
        parent[a] = 0;
        parent[b] = 0;
        return;
    }

    if (a > b) swap(a, b);
    parent[b] = a;
}

int cnt = 0;
for (int i = 0; i < M; i++)
{
    int a, b;
    cin >> a >> b;

    Union(a, b);
}

for (int i = 1; i <= N; i++)
{
    if (parent[i] == i) cnt++;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M;

vector<vector<int>> graph;
vector<bool> visited;

bool Dfs(int start, int prev)
{
    visited[start] = true;
    for (auto node : graph[start])
    {
        if (node == prev) continue;

        if (visited[node]) return false;
        if (!Dfs(node, start)) return false;
    }

    return true;
}

int main() 
{
    INPUT_OPTIMIZE;

    int t = 1;
    while (true)
    {
        cin >> N >> M;
        if (N == 0 && M == 0) break;

        graph.resize(N + 1, vector<int>());
        visited.resize(N + 1);

        for (int i = 1; i <= N; i++)
        {
            graph[i].clear();
            visited[i] = false;
        }

        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;

            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        int cnt = 0;
        for (int i = 1; i <= N; i++)
        {
            if (visited[i]) continue;
            if (Dfs(i, 0)) cnt++;
        }

        if (cnt > 1)
        {
            cout << "Case " << t++ << ": A forest of " << cnt << " trees.\n";

        }
        else if (cnt == 1)
        {
            cout << "Case " << t++ << ": There is one tree.\n";

        }
        else
        {
            cout << "Case " << t++ << ": No trees.\n";
        }
    }

    return 0;
}

---