선인장 그래프 (Cactus Graph)

정의

선인장 그래프 (Cactus Graph) 는 모든 간선이 최대 한 개의 단순 사이클에만 포함되는 무방향 연결 그래프. 트리 (tree) 의 일반화로, 사이클은 허용하되 “사이클끼리 간선을 공유하지 않음”.

형태: 여러 사이클이 점 (정점) 으로만 연결된 구조. 간선 수 E ≤ V + (사이클 수 - 1), 트리면 E = V - 1.

문제 상황과 동기

일반 그래프는 사이클이 복잡하게 엉켜 DP / 최단 경로 / 매칭이 NP-hard. 트리는 선형 시간 가능하지만 사이클 없음. 선인장은 사이클이 있으면서도 트리와 비슷한 구조적 성질을 보존.

naive: 일반 그래프 알고리즘 O(V^2) 또는 O(V E). 핵심 통찰: 각 사이클을 “super-node” 로 축약하면 트리 → DFS / DP 가능. 사이클 내부는 별도 처리.

PS 에서: “도로망에 사이클 하나”, “회로 네트워크 (공유 안 함)”, BOJ 지름 / 최단 경로 변형.

시각화

핵심 아이디어

invariant

간선 e 는 최대 하나의 사이클 C 에만 속함. 두 사이클이 간선을 공유하지 않음 → 간선 분할 (edge partition) 이 깔끔.

DFS 기반 분해

1. DFS tree 를 만든다.
2. back edge (u, v) 가 나오면 u → v 경로 + (u, v) 가 사이클 C.
3. C 의 간선들을 “이미 사이클에 포함됨” 마킹. 다른 back edge 가 C 의 간선을 다시 쓰면 선인장 아님.

시간 O(V + E), 공간 O(V).

DP on cactus

1. 각 사이클을 “구간” 으로 보고 사이클 내 DP.
2. 사이클을 하나의 노드로 축약한 트리에서 tree DP.
3. 둘 합치기: 사이클 DP → 트리 DP.

예: 선인장 지름 = max(트리 지름, 각 사이클 내 최대 거리).

알고리즘

is_cactus(G):
    visited = [false] * V
    edge_used = set()
    for root in V:
        if not visited[root]:
            if not dfs_cactus(root, -1, visited, edge_used):
                return false
    return true

dfs_cactus(u, parent, visited, edge_used):
    visited[u] = true
    for v in adj[u]:
        if v == parent: continue
        edge = (min(u,v), max(u,v))
        if visited[v]:
            # back edge
            if edge in edge_used:
                return false   # 이미 다른 사이클에 속함
            path = trace_path(u, v)
            for e in path:
                if e in edge_used:
                    return false
                edge_used.add(e)
        else:
            if not dfs_cactus(v, u, visited, edge_used):
                return false
    return true

구현

// 선인장 그래프 검증: DFS + back edge 중복 체크
#include <bits/stdc++.h>
using namespace std;
​
vector<vector<int>> adj;
vector<int> parent, depth;
set<pair<int,int>> cycleEdges;
bool isCactus;
​
void dfs(int u, int p, int d) {
  parent[u] = p;
  depth[u] = d;
  for (int v : adj[u]) {
      if (v == p) continue;
      auto edge = minmax(u, v);
      if (depth[v] == -1) {
          dfs(v, u, d + 1);
      } else if (depth[v] < depth[u]) {
          // back edge u -> v
          // trace cycle
          for (int x = u; x != v; x = parent[x]) {
              auto e = minmax(x, parent[x]);
              if (cycleEdges.count(e)) { isCactus = false; return; }
              cycleEdges.insert(e);
          }
          if (cycleEdges.count(edge)) { isCactus = false; return; }
          cycleEdges.insert(edge);
      }
  }
}
​
int main() {
  int n, m; cin >> n >> m;
  adj.resize(n); parent.resize(n, -1); depth.resize(n, -1);
  isCactus = true;
  for (int i = 0; i < m; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  for (int i = 0; i < n; i++)
      if (depth[i] == -1) dfs(i, -1, 0);
  cout << (isCactus ? "cactus" : "not cactus") << "\n";
}

# 선인장 그래프 판별
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
​
def is_cactus(n, edges):
  adj = [[] for _ in range(n)]
  for u, v in edges:
      adj[u].append(v)
      adj[v].append(u)
  parent = [-1] * n
  depth = [-1] * n
  cycle_edges = set()
  result = [True]
​
  def dfs(u, p, d):
      parent[u], depth[u] = p, d
      for v in adj[u]:
          if v == p:
              continue
          edge = (min(u, v), max(u, v))
          if depth[v] == -1:
              dfs(v, u, d + 1)
          elif depth[v] < depth[u]:
              # back edge
              x = u
              while x != v:
                  e = (min(x, parent[x]), max(x, parent[x]))
                  if e in cycle_edges:
                      result[0] = False
                      return
                  cycle_edges.add(e)
                  x = parent[x]
              if edge in cycle_edges:
                  result[0] = False
                  return
              cycle_edges.add(edge)
​
  for i in range(n):
      if depth[i] == -1:
          dfs(i, -1, 0)
  return result[0]
​
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
print("cactus" if is_cactus(n, edges) else "not cactus")

5 6
0 1
1 2
2 0
2 3
3 4
4 2

cactus

4 5
0 1
1 2
2 0
0 2
2 3

not cactus

복잡도

변형 / 활용

1. 선인장 지름

각 사이클 내 최대 거리 + 트리 지름. 사이클을 “무게 중심” 으로 축약.

2. 선인장 최단 경로

Dijkstra / BFS. 사이클 구조가 트리와 비슷해 일반 그래프보다 빠름.

3. 선인장 DP

부분합 DP, 매칭, 독립 집합 모두 O(V + E). 일반 그래프는 NP.

4. 방향 선인장

각 간선이 최대 한 사이클. functional graph 의 변형.

함정

1. 간선 공유 놓침

두 사이클이 정점을 공유해도 OK. 간선을 공유하면 NO.

  O---O
  |\ /|
  | X |  ← 간선 (중앙 교차) 공유 → 선인장 아님
  |/ \|
  O---O

2. back edge 중복 처리

같은 back edge 를 두 번 방문하면 잘못된 판단. set 으로 관리.

3. 비연결 그래프

선인장 정의는 “연결 그래프”. 비연결이면 각 컴포넌트 따로 판별.

4. DP 순서

사이클 내부 DP → 트리 DP 순서. 역순이면 값 꼬임.

BOJ 연습 문제

참고

• 트리
• 깊이 우선 탐색
• 사이클 탐지
• 그래프 동적 계획법