그래프 이론: 단 하나의 사이클을 갖는 기환수(Base Ring Tree) 구조와 계산 접근법

기환수의 기본 정의와 특성

정점의 수가 $N$이고 간선의 수도 $N$개인 연결 그래프를 기환수(Unicyclic Graph)라고 합니다. 일반적인 트리는 $N$개 정점에 $N-1$개 간선을 가지므로, 간선이 하나 추가되면 정확히 하나의 사이클(Cycle)이 형성됩니다. 기환수는 항상 고리를 중심으로 여러 개의 서브트리가 뻗어 나오는 형태를 띠며, 방향성이 부여된 경우 두 가지 대표 구조로 분류됩니다.

  • 내향 기환수(Inward Base Ring Tree): 모든 정점의 진출 차수(Out-degree)가 1인 방향성 그래프
  • 외향 기환수(Outward Base Ring Tree): 모든 정점의 진입 차수(In-degree)가 1인 방향성 그래프

응용 사례 1: 사이클 기반 경로 카운팅 (조합론)

무방향 기환수에서 모든 정점 쌍 사이의 단순 경로(Simple Path) 총합을 구하는 문제입니다. 사이클 위에서는 경로가 왕복할 수 있으므로, 사이클 정점에서 뻗어 나가는 서브트리의 크기(Subtree Size)를 기준으로 경로를 분리하여 계산합니다. 구현 시 차수(Degree)가 1인 리프 노드를 순차적으로 제거(Pruning)하는 방식으

남아 있는 정점 집합이 바로 사이클임을 선형 시간复杂度로 확인할 수 있습니다. 이후 각 사이클 정점을 루트로 하여 DFS를 실행하고, 서브트리 내 경로와 사이클을 가로지르는 경로를 조합론 공식에 대입하여 누적합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;
using ll = long long;

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    vector<vector<int>> adj(n + 1);
    vector<int> degree(n + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) q.push(i);
    }

    while (!q.empty()) {
        int curr = q.front(); q.pop();
        for (int next : adj[curr]) {
            if (--degree[next] == 1) {
                q.push(next);
            }
        }
    }

    vector<bool> is_cycle(n + 1, false);
    vector<int> cycle_vertices;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 1) {
            is_cycle[i] = true;
            cycle_vertices.push_back(i);
        }
    }

    auto get_subtree_size = [&](int root) {
        vector<bool> visited(n + 1, false);
        int cnt = 0;
        function<void(int)> traverse = [&](int u) {
            visited[u] = true;
            cnt++;
            for (int v : adj[u]) {
                if (!visited[v] && !is_cycle[v]) {
                    traverse(v);
                }
            }
        };
        traverse(root);
        return cnt;
    };

    ll total_paths = 0;
    ll external_cnt = 0; 

    for (int cv : cycle_vertices) {
        ll sub_sz = get_subtree_size(cv);
        // 서브트리 내부 단순 경로 조합
        total_paths += sub_sz * (sub_sz - 1) / 2;
        // 사이클을 통해 연결되는 타 서브트리 경로
        total_paths += (sub_sz - 1) * (n - sub_sz - external_cnt) * 2;
        external_cnt += sub_sz - 1;
    }

    // 사이클 자체를 구성하는 경로
    ll c_sz = cycle_vertices.size();
    total_paths += c_sz * (c_sz - 1);

    cout << total_paths << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

응용 사례 2: 내향 그리드 상의 제약 전파 (순환 검증)

각 노드가 다음 상태나 타 노드를 지시하며 제약 조건을 따르는 함수형 그래프(Functional Graph) 문제입니다. 외부 체인(Node Chain)은 사이클의 상태 결정에 따라 일괄 확정되므로, 실제 해의 개수 계산은 사이클 구성원소의 상태 조합만 고려하면 됩니다. 사이클 내 임의 한 정점의 초기값을 후보 집합 중 하나로 가정하면, 사이클을 한 번 순회하며 제약 조건을 만족하는지 검증 가능합니다. 모든 가능 초기 값에 대해 검증 결과를 모듈로 연산으로 누적 곱하면 최종 답을 얻을 수 있습니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;

const int MOD = 998244353;

int resolve_rule(const string& constraint, int idx) {
    return constraint[idx] - 'A';
}

void solve() {
    int n;
    if (!(cin >> n)) return;

    vector<int> target(n + 1);
    vector<string> rules(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> target[i] >> rules[i];
    }

    vector<bool> processed(n + 1, false);
    ll result_combinations = 1;

    for (int start_node = 1; start_node <= n; ++start_node) {
        if (processed[start_node]) continue;

        int curr = start_node;
        vector<int> path;
        vector<int> cycle_segment;

        // 현재 탐색 경로를 추적하며 사이클 감지
        while (!processed[curr]) {
            processed[curr] = true;
            path.push_back(curr);
            curr = target[curr];
            
            // 현재 스택에 이미 방문한 정점이 나오면 사이클 시작 지점
            auto it = find(path.begin(), path.end(), curr);
            if (it != path.end()) {
                cycle_segment.assign(it, path.end());
                break;
            }
        }

        if (cycle_segment.empty()) continue;

        int valid_configs = 0;
        // 사이클 첫 노드의 5가지 가능한 초기 상태 시도
        for (int init_val = 0; init_val < 5; ++init_val) {
            int current_state = init_val;
            
            for (int node : cycle_segment) {
                current_state = resolve_rule(rules[node], current_state);
            }

            // 순환 후 원래 상태로 돌아오는지 검증
            if (current_state == init_val) {
                valid_configs++;
            }
        }

        result_combinations = (result_combinations * valid_configs) % MOD;
    }

    cout << result_combinations << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

태그: 그래프이론 단일사이클그래프 기환수 사이클추출 경로카운팅

10월 13일 09:37에 게시됨