백준 26358, 26359 - A Prickly Problem – Black Edition (C++)

문제

• 문제 링크

  
   BOJ 26359 - A Prickly Problem – Black Edition 
  

• 문제 요약

$V$개의 정점으로 이루어진 $Cactus$ $Graph$가 주어진다.
스패닝 트리가 되도록 $V-1$개의 간선만을 남겼을 때, 서로 다른 모양의 트리가 존재할 수 있다.
이 스패닝 트리의 가짓수에 대해 $1,007$로 나눈 나머지를 출력하자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ V ≤ 50,000$

$1 ≤ E ≤ (3*V)/2$

주어지는 그래프는 $Cactus$ $Graph$임이 보장된다.

입력은 여러 개의 테스트 케이스로 이루어져 있다.

알고리즘 분류

• 그래프 이론 (graphs)
• 이중 연결 요소 (biconnected_component)
• 선인장 (cactus)

풀이

어떤 스패닝 트리를 만들기 위해 간선 $E$를 제거할 때, $E$가 $articulation$ $edge$라면 제거할 수 없다.
즉, 우리가 제거한다고 가정해야 할 $E$는 반드시 단순 사이클 위에 있는 간선이어야 한다.

주어진 그래프에서, $biconnected$ $component$들을 모두 찾아내어보자.

$1$개의 간선을 포함한 컴포넌트도 $biconnected$ $component$의 정의에 부합한다.
그러나, 지금은 단순 사이클만이 필요하기 때문에 이들은 제외해야 함을 유의하자.

---

찾은 컴포넌트들을 $bcc_1, bcc_2, ... , bcc_k$라 할 때, 어떻게 스패닝 트리를 만들 수 있을까?

이는 존재하는 모든 사이클들을 끊어주면 되므로, 각 $bcc$에서 간선을 하나씩 지워주면 된다.

문제에서는 가짓수를 묻고 있으므로, 답은 $(Size(bcc_1) * Size(bcc_2) * ... * Size(bcc_k))$ $mod$ $1007$가 된다.

따라서 $bcc$들을 저장할 때 실제 구성 원소들을 갖고 있을 필요는 없고, 규모만 저장하면 된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <int> Gr[50001];
vector <int> bcc;
stack <int> st;
 
int in[50001];
int n, m, cur;
 
void Input()
{
    scanf("%d %d", &n, &m);
    for (int u, v; m--;)
    {
        scanf("%d %d", &u, &v);
        Gr[u].push_back(v);
        Gr[v].push_back(u);
    }
}
int DFS(int now, int prev)
{
    int _min(in[now] = ++cur);
    for (int& nxt : Gr[now])
        if (nxt ^ prev)
        {
            if (in[now] > in[nxt]) st.push(nxt);
            if (!in[nxt])
            {
                int temp(DFS(nxt, now));
                if (temp >= in[now])
                {
                    int sz{};
                    while (1)
                    {
                        int top(st.top()); st.pop();
                        sz++;
                        if (top == nxt) break;
                    }
                    if (sz > 1) bcc.push_back(sz);
                }
                _min = min(_min, temp);
            }
            _min = min(_min, in[nxt]);
        }
    return _min;
}
void End(int tc, int ans = 1)
{
    for (int& cnt : bcc)
        ans = (ans * cnt) % 1007;
    printf("Case #%d: %d\n\n", tc, ans);
 
    bcc = {}, st = {}, cur = 0;
    for (int i{}; i <= n; i++)
    {
        Gr[i].clear();
        in[i] = 0;
    }
}
int main()
{
    int t; scanf("%d", &t);
    for (int tc(1); tc <= t; tc++)
    {
        Input();
        DFS(1, 1);
        End(tc);
    }
}

comment

끝