[ICPC] 백준 20040 - 사이클 게임

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

힌트

유니온 파인드를 사용하면 그래프의 사이클 존재 여부를 빠르게 판별할 수 있다.

---

풀이

각 정점을 이어나갈 때 사이클이 어느 순서에 생기는지 알아야 하는 문제이다.

 

각 정점을 이을 때마다 DFS를 이용한 사이클 검출을 실시하면 $O(m^{2})$의 시간 복잡도로 인해 시간 초과를 받을 것이다.

 

하지만 유니온 파인드를 이용하면 아주 짧은 시간으로 사이클 여부를 판단할 수 있다.

 

각 정점을 union 하면서 만약 부모가 같은 정점을 마주치면 트리 상태에서 간선을 한 개 추가하는 것이므로 곧 사이클이 존재하는 그래프가 됨을 알 수 있다.

 

m개의 쿼리를 진행하면서 사이클이 생기는지 검사하도록 하자.

 

전체 코드

#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>;
using pll = pair<ll, ll>;

int n, m;

struct ufind
{
  vector<int> parent, rank;

  ufind(int n): parent(n), rank(n)
  {
    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 false;

    if (rank[v] < rank[u])
      swap(u, v);
    parent[u] = v;

    if (rank[u] == rank[v])
      ++rank[v];

    return true;
  }
};

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

  cin >> n >> m;

  ufind st(n);

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

    if (st.vnion(a, b))
      continue;
    else
    {
      cout << i + 1;
      return 0;
    }
  }

  cout << 0;
}

제출 기록