[ICPC] 백준 4803 - 트리

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

힌트

주어진 포레스트에 어떤 상태들이 존재할 수 있는지 생각해보자.

풀이

주어진 포레스트에서 트리의 개수를 찾는 문제이다.

 

포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다.

 

각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다.

 

노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다.

 

유니온 파인드를 사용할 때는 그래프와 트리가 연결되는 경우를 조심하도록 한다.

 

전체 코드 - 유니온 파인드로 구현했다.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;
unordered_set<int> cnt;

struct ufind
{
  vector<int> parent, rank;
  vector<bool> istree;

  ufind(int n): parent(n), rank(n), istree(n, true)
  {
    for (int i = 0; i < n; ++i)
      parent[i] = i;
  }

  int find(int u)
  {
    if (u == parent[u]) return u;
    return parent[u] = find(parent[u]);
  }

  bool vnion(int u, int v)
  {
    u = find(u), v = find(v);
    if (u == v) return istree[u] = false;
    if (rank[u] > rank[v])
      swap(u, v);
    bool ret = !(!istree[u] || !istree[v]);
    parent[u] = v;
    if (rank[v] == rank[u])
      ++rank[v];
    return istree[v] = ret;
  }
};

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  int idx = 1;

  while (n || m)
  {
    cnt.clear();
    ufind st(n + 1);
  
    for (int i = 0; i < m; ++i)
    {
      int a, b;
      cin >> a >> b;
      st.vnion(a, b);
    }

    for (int i = 1; i <= n; ++i)
      cnt.insert(st.find(i));

    int trees = 0;
    for (int i: cnt)
    {
      if (st.istree[st.find(i)])
        ++trees;
    }

    cout << "Case " << idx;

    if (!trees)
    {
      cout << ": No trees.\n";
    }
    else
    {
      if (trees == 1)
      {
        cout << ": There is one tree.\n";
      }
      else
      {
        cout << ": A forest of " << trees << " trees.\n";
      }
    }

    ++idx;
    cin >> n >> m;
  }
}

제출 기록

작성자도 낚였다.