📖 문제 이해하기 선인장(Cactus) 그래프는 그래프 이론에서 특별한 성질을 가진 연결 그래프입니다. 핵심은 각 정점이 최대 하나의 단순 사이클에만 속할 수 있다는 제약입니다. 다시 말해, 어떤 정점도 두 개 이상의 서로 다른 사이클의 일부가 될 수 없습니다. 예를 들어, 정점이 4개이고 간선이 (1,2), (2,3), (3,4), (4,1)인 그래프를 생각해보겠습니다. 이는 하나의 사이클 1→2→3→4→1을 형성하며, 각 정점은…
📖 문제 이해하기 단절선 문제는 주어진 그래프에서 “제거했을 때 연결 요소의 개수가 증가하는 간선”을 모두 찾는 문제입니다. 쉽게 말해, 어떤 다리를 끊었을 때 원래 하나였던 섬이 두 개로 분리되는 그 다리를 찾는 것입니다. 예를 들어, 정점 5개와 간선 5개로 구성된 그래프가 있다고 해봅시다: 1-2, 2-3, 3-4, 3-5, 4-5. 여기서 간선 1-2나 2-3을 제거하면 그래프가 두…
https://www.acmicpc.net/problem/2150 📖 문제 이해하기 강한 연결 요소란 방향 그래프에서 정점들의 최대 부분집합으로, 그 집합에 속한 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 의미합니다. 예를 들어, 정점 집합 {1, 2, 3}이 SCC라면 1→2→3→1과 같은 순환 경로가 가능해야 하며, 실제로는 더 복잡한 연결 구조를 가질 수 있습니다….