BOJ 2111 - 선인장 링크
(2023.06.22 기준 P2)

문제

그래프가 주어질 때, 간선 선인장이 아닐 경우엔 0을 출력, 아니면 스패닝 서브그래프의 개수 출력

알고리즘

이중 연결 요소를 이용하여 간선 선인장인지 구분 후..

풀이

정점 선인장 풀이에 적어놓았듯이 간선 선인장의 조건은 단순 사이클이기만 하면 된다. 즉, 간선의 개수가 3 이상인 BCC의 정점 개수와 간선 개수가 일치하면 된다.

중요한 점은 연결 그래프이냐다. 스패닝 서브그래프는 말 그대로 모든 정점들이 연결되어 있어야 한다. 근데 주어지는 그래프가 처음부터 연결 그래프가 아니라면? 스패닝 서브그래프의 개수는 0이 된다. 그러므로, 아무 정점 하나에서만 DFS를 돌리고 방문하지 않은 정점이 있는지 확인하여 연결 그래프인지 확인하자.

간선 선인장이면서 연결 그래프이면 이제 스패닝 서브그래프의 개수를 구해야 한다.


단순 사이클은 정점의 개수와 간선의 개수가 같다.
스패닝 그래프. 즉, 트리는 정점의 개수는 간선의 개수 + 1이다.
그렇다면 위 그림처럼 한 사이클마다 간선을 최대 하나만 지울 수 있다. 물론, 지우지 않을 수도 있다.
그러면 한 사이클(BCC)마다 경우의 수는 간선의 개수 + 1이 나온다.
이를 모든 사이클(BCC)의 경우의 수를 전부 곱하면 된다.

주의사항

정수 타입별 범위가 유의미한 언어에선 큰 수 곱셈을 따로 구현해야 한다.
LL, ULL 전부 통하지 않는다.
물론, 큰 수 곱셈은 O(N^2)으로 구현해도 무방하다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 20000;

int lv[MAXN];
stack<pii> stk;
vector<int> graph[MAXN];
vector<vector<pii>> bcc;

vector<int> mul(vector<int> A, int B){ // 큰 수 곱셈 (vector 형태로 숫자 순서가 반대로 되게 반환)
    int asz = A.size(), rsz = asz, p = 0, n;
    vector<int> result(rsz);
    while (B){
        n = B % 10; B /= 10;
        result.resize(++rsz);
        for (int i = 0; i < asz; i++) result[i + p] += A[i] * n;
        p++;
    }

    for (int i = 0, n; i < rsz; i++){
        n = result[i] % 10;
        result[i + 1] += (result[i] - n) / 10;
        result[i] = n;
    }

    if (!result[rsz - 1]) result.resize(--rsz);

    return result;
}

// biconnected component
int dfs(int i, int p){
    int result = lv[i];

    for (auto j: graph[i]){
        if (j == p) continue;

        // i-j 간선이 사용되지 않았다면 스택에 추가
        if (lv[i] > lv[j]) stk.push({i, j});

        // j가 방문하지 않은 정점이라면
        if (lv[j] == -1){
            lv[j] = lv[i] + 1;
            int nxt = dfs(j, i);

            // j로의 dfs 결과가 dfs 스패닝 트리 상 i의 조상 정점으로 갈 수 없다는 결과라면
            // 새 BCC를 발견한 것이다.
            if (nxt >= lv[i]){
                vector<pii> bcc_element; // 발견한 BCC를 이루는 간선을 저장할 것이다.
                pii find = {i, j}; // BCC의 첫 간선을 찾아나가야 한다.
                while (!stk.empty() && stk.top() != find){ // 간선을 찾을 때까지 빼내서 저장
                    bcc_element.push_back(stk.top()); stk.pop();
                }
                bcc_element.push_back(stk.top()); stk.pop();
                bcc.push_back(bcc_element); // 저장된 간선들은 BCC를 이룬다.
            }
            result = min(result, nxt);
        }
        else result = min(result, lv[j]); // 역방향 간선은 방문 순서만 따로 결과랑 비교
    }

    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;

    vector<int> route;
    for (int i = 0, n; i < M; i++){
        cin >> n; route.clear();
        for (int j = 0, x; j < n; j++) cin >> x, route.push_back(--x);

        for (int j = 0; j + 1 < n; j++)
            graph[route[j]].push_back(route[j + 1]), graph[route[j + 1]].push_back(route[j]);
    }

    lv[0] = 0; fill(lv + 1, lv + N, -1);
    dfs(0, -1);

    for (int i = 1; i < N; i++)
        if (lv[i] == -1){ // 연결 그래프가 아니면 스패닝 서브그래프가 생길 수 없다.
            cout << 0;
            return 0;
        }

    vector<int> result = {1};
    for (int i = 0, n = bcc.size(); i < n; i++){
        // 간선 개수가 1이면 사이클이 생기지 않는다.
        // 그러므로 이 간선을 끊으면 스패닝 서브그래프가 될 수 없다.
        if (bcc[i].size() == 1) continue;

        vector<int> vertex; // BCC를 이루는 정점 번호 저장
        for (auto [x, y]: bcc[i]) vertex.push_back(x), vertex.push_back(y);

        // 저장된 정점들의 중복을 제거한 후
        // 정점 개수와 간선 개수가 일치하는지 확인
        sort(vertex.begin(), vertex.end());
        vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());

        if (vertex.size() == bcc[i].size()) // 선인장 조건을 만족하는 BCC이면
            // 간선을 하나만 지우거나 지우지 않을 수 있으므로
            // 가능한 스패닝 서브그래프는 정점 개수 + 1
            result = mul(result, vertex.size() + 1); // 모든 경우의 수이므로 곱하자.

        else{ // 선인장 조건을 만족하지 않는다면 0 출력
            cout << 0;
            return 0;
        }
    }

    // 결과는 숫자가 반대로 저장되어 있어서 반대로 출력하자.
    for (int i = result.size() - 1; i >= 0; i--) cout << result[i];
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(22222)

# biconnected component
def dfs(i, p):
    result = lv[i]

    for j in graph[i]:
        if j == p:
            continue

        # i-j 간선이 사용되지 않았다면 스택에 추가
        if lv[i] > lv[j]:
            stk.append((i, j))

        # j가 방문하지 않은 정점이라면
        if lv[j] == -1:
            lv[j] = lv[i] + 1
            nxt = dfs(j, i)

            # j로의 dfs 결과가 dfs 스패닝 트리 상 i의 조상 정점으로 갈 수 없다는 결과라면
            # 새 BCC를 발견한 것이다.
            if nxt >= lv[i]:
                bcc_element = [] # 발견한 BCC를 이루는 간선을 저장할 것이다.
                find = (i, j) # BCC의 첫 간선을 찾아나가야 한다.
                while stk and stk[-1] != find:
                    bcc_element.append(stk.pop())
                bcc_element.append(stk.pop())
                bcc.append(bcc_element) # 저장된 간선들은 BCC를 이룬다.

            result = min(result, nxt)

        else: # 역방향 간선은 방문 순서만 따로 결과랑 비교
            result = min(result, lv[j])

    return result

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    n, *route = map(int, input().split())
    for j in range(n - 1):
        graph[route[j] - 1].append(route[j + 1] - 1)
        graph[route[j + 1] - 1].append(route[j] - 1)

lv = [-1] * N; lv[0] = 0
bcc = []; stk = []
dfs(0, -1)

for i in range(1, N):
    if lv[i] == -1: # 연결 그래프가 아니면 스패닝 서브그래프가 생길 수 없다.
        print(0)
        exit()

result = 1
for i in range(len(bcc)):
    # 간선 개수가 1이면 사이클이 생기지 않는다.
    # 그러므로 이 간선을 끊으면 스패닝 서브그래프가 될 수 없다.
    if len(bcc[i]) == 1:
        continue

    vertex = [] # BCC를 이루는 정점 번호 저장
    for x, y in bcc[i]:
        vertex.append(x); vertex.append(y)

    # 저장된 정점들의 중복을 제거한 후
    # 정점 개수와 간선 개수가 일치하는지 확인

    if len(set(vertex)) == len(bcc[i]): # 선인장 조건을 만족하는 BCC이면
        # 간선을 하나만 지우거나 지우지 않을 수 있으므로
        # 가능한 스패닝 서브그래프는 정점 개수 + 1 (= 간선 개수 + 1)
        result *= len(bcc[i]) + 1 # 모든 경우의 수이므로 곱하자.

    else: # 선인장 조건을 만족하지 않는다면 0 출력
        print(0)
        exit()

print(result)