백준 21025 - Healthy Lifestyle (C++)

문제

• 문제 링크

  
   BOJ 21025 - Healthy Lifestyle 
  

• 문제 요약

$N$개의 정점과, 이들을 잇는 $M$개의 간선으로 이루어진 그래프가 주어진다.
아래의 쿼리를 수행하는 프로그램을 작성하자.



$u$ $v$ : $u$에서 $v$로 가는 서로 다른 경로가 존재하면 $YES$, 존재하지 않는다면 $NO$를 출력한다.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, M, Q ≤ 10^5$

알고리즘 분류

• 그래프 이론 (graphs)
• 이중 연결 요소 (biconnected_component)
• 자료 구조 (data_structures)
• 분리 집합 (disjoint_set)

풀이

간단히 생각해보면, 답이 $YES$인 경우는 $u, v$가 같은 사이클에 속할 때 뿐이라는 것을 알 수 있다.
그리고, 한 $articulation$ $point$를 기준으로 $2$개 이상의 사이클이 형성될 수 있는데 이들 간에 이동할 때 역시 $YES$이다.

그래프 상에 존재하는 모든 $biconnected$ $component$들을 찾아내자.

이제 같은 컴포넌트에 속한 정점들을 식별할 수 있는 무언가가 필요한데, 나같은 경우 분리 집합으로 묶어주었다.
이 과정에선 다양한 방식이 있을 것 같으니 편한 방식을 택하면 될 듯 하다.

전체 코드

#include<bits/stdc++.h>
#define pii pair<int, int>
#define N 100001
using namespace std;
 
vector <int> Gr[N], in(N), par(N);
 
int find(int x) { return par[x] = par[x] ^ x ? find(par[x]) : x; }
void merge(int x, int y) { x > y ? par[x] = y : par[y] = x; }
 
stack <pii> st; int cur;
int DFS(int now, int prev)
{
    int _min(in[now] = ++cur);
    for (int& nxt : Gr[now])
    {
        if (nxt == prev) continue;
        if (in[now] > in[nxt]) st.push({ now, nxt });
        if (!in[nxt])
        {
            int temp(DFS(nxt, now));
            if (in[now] <= temp)
            {
                vector <pii> V;
                while (1)
                {
                    auto top(st.top()); st.pop();
                    V.push_back(top);
                    if (top == pii(now, nxt)) break;
                }
                if (V.size() > 1)
                    for (auto& [u, v] : V)
                        merge(find(u), find(v));
            }
            _min = min(_min, temp);
        }
        _min = min(_min, in[nxt]);
    }
    return _min;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    for (int u, v; m--;)
    {
        cin >> u >> v;
        Gr[u].push_back(v);
        Gr[v].push_back(u);
    }
 
    iota(par.begin(), par.end(), 0);
    DFS(1, 1);
 
    for (int u, v; q--;)
    {
        cin >> u >> v;
        cout << (find(u) ^ find(v) ? "NO" : "YES") << '\n';
    }
}

comment

끝