기순환 트리의 개념

기순환 트리는 n개의 노드와 n개의 간선을 가지는 그래프 구조입니다. 트리가 아니며 단일 순환 구조를 가집니다.

무방향 그래프에서의 기순환 트리

n개의 노드와 n개의 간선을 가진 연결된 무방향 그래프로, 하나의 순환을 포함합니다. 연결되지 않은 경우 기순환 트리 숲으로 구성됩니다.

방향 그래프에서의 기순환 트리

내향성 트리

각 노드에서 나가는 간선이 정확히 하나 존재합니다.

외향성 트리

각 노드로 들어오는 간선이 정확히 하나 존재합니다.

기순환 트리 처리 방법

핵심 접근법

1. 유일한 순환 구조 탐색
2. 순환 외부 영역을 트리로 처리
3. 순환과 결합한 계산 수행

순환 탐색 기법

DFS 기반 탐색 로직

1. 임의 노드에서 탐색 시작
2. 방문 노드는 회색, 백트래킹 노드는 검정색 표시
3. 미방문 간선을 통해 회색 노드 접근 시 대상 노드를 빨간색으로 표시
4. 백트래킹 경로상 노드를 주황색으로 표시
5. 빨간색 노드 도달 시 알고리즘 종료

주요 고려사항

• 무방향 그래프에서 간선 표시는 양방향 처리
• 기순환 트리 숲 처리 시 연결 요소 식별 필요
• 분리 집합 또는 추가 탐색을 통한 영역 구분

구현 예시

bool findCycle(int node, int parent) {
  if (visited[node] == 1) {
    visited[node] = 2;
    cycleNodes[++count] = node;
    return true;
  }
  visited[node] = 1;
  
  for (auto& edge : adj[node]) {
    if (edge.used) continue;
    edge.used = true;
    adj[edge.to].used = true;
    
    if (findCycle(edge.to, node)) {
      if (visited[node] != 2) {
        cycleNodes[++count] = node;
        return true;
      }
      return false;
    }
  }
  return false;
}

후속 처리 전략

순환 외부 영역은 트리 DP로 처리하고, 순환 영역은 선형 DP와 원형 처리 기법 적용:

• 순환 노드를 선형으로 확장(2배 복제)
• 슬라이딩 윈도우 최적화

응용 문제 사례

기능성 그래프 도달성

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> next(n+1);
  for (int i = 1; i <= n; i++) cin >> next[i];
  
  vector<int> visited(n+1), dp(n+1);
  
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;
    int cur = i;
    while (true) {
      if (visited[cur]) {
        if (visited[cur] == i) {
          int start = cur, cycleSize = 1;
          for (int temp = next[cur]; temp != start; temp = next[temp]) 
            cycleSize++;
          for (int temp = cur; dp[temp] == 0; temp = next[temp])
            dp[temp] = cycleSize;
          break;
        }
      }
      visited[cur] = i;
      cur = next[cur];
    }
  }
  
  function<int(int)> calcDP = [&](int node) {
    if (dp[node]) return dp[node];
    return dp[node] = calcDP(next[node]) + 1;
  };
  
  long total = 0;
  for (int i = 1; i <= n; i++) total += calcDP(i);
  cout << total;
  return 0;
}

K-순열 변환

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  long k;
  cin >> n >> k;
  vector<vector<int>> ancestor(60, vector<int>(n+1));
  
  for (int i = 1; i <= n; i++) 
    cin >> ancestor[0][i];
  
  for (int j = 1; j < 60; j++)
    for (int i = 1; i <= n; i++)
      ancestor[j][i] = ancestor[j-1][ancestor[j-1][i]];
  
  vector<int> values(n+1);
  for (int i = 1; i <= n; i++) 
    cin >> values[i];
  
  for (int i = 1; i <= n; i++) {
    int pos = i;
    for (int bit = 0; bit < 60; bit++)
      if (k & (1LL << bit))
        pos = ancestor[bit][pos];
    cout << values[pos] << " ";
  }
  return 0;
}