기환수의 기본 정의와 특성
정점의 수가 $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;
}