📖 문제 이해하기 이 문제는 그래프 이론에서 핵심적인 개념인 절단점(Articulation Point)과 브리지(Bridge)를 활용하여 그래프의 연결성을 판단하는 문제입니다. 문제에서는 N개의 도시와 E개의 양방향 도로로 이루어진 연결된 그래프가 주어집니다. 우리는 두 가지 유형의 질문에 답해야 합니다: 예를 들어, 도시 1-2-3-4가 일직선으로 연결된 그래프에서 도시 2와 3을 잇는 도로를 제거하면, 도시 1에서 도시 4로 갈 수 없게 됩니다….
📖 문제 이해하기 선인장(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을 제거하면 그래프가 두…
📖 문제 해석 이 문제는 무방향 그래프에서 모든 단절점을 찾아 오름차순으로 출력하는 것입니다. 예를 들어, 5개의 정점이 있는 그래프에서 정점 1이 정점 2, 3과 연결되고, 정점 2가 정점 4, 5와 연결된 상황을 생각해봅시다. 만약 정점 2를 제거한다면 {1, 3}과 {4, 5}라는 두 개의 분리된 성분이 만들어지므로, 정점 2는 단절점이 됩니다. 주목할 점은 입력 그래프가 반드시…
https://www.acmicpc.net/problem/2150 📖 문제 이해하기 강한 연결 요소란 방향 그래프에서 정점들의 최대 부분집합으로, 그 집합에 속한 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 의미합니다. 예를 들어, 정점 집합 {1, 2, 3}이 SCC라면 1→2→3→1과 같은 순환 경로가 가능해야 하며, 실제로는 더 복잡한 연결 구조를 가질 수 있습니다….