절단점 찾기 알고리즘
어떤 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점을 절단점이라고 한다.
어떤 정점이 절단점인지 판단하는 기본적인 방법은 해당 정점을 그래프에서 삭제했을 때, 컴포넌트의 개수가 증가했는지를 확인하는 것이다.
이 방법을 활용하면 깊이 우선 탐색을 정점의 개수 만큼 V번을 실행해야 한다. 하지만 앞서 배운 정보들을 활용하면 한 번의 깊이 우선 탐색만으로 그래프의 모든 절단점을 찾아낼 수 있다.
무방향 그래프에서 깊이 우선 탐색을 수행해 DFS스패닝 트리를 만들면 임의의 정점 u와 연결된 정점들은 모두 u의 선조가 아니면 자손이다. 무방향 DFS스패닝 트리는 교차간선이 없기 때문에 u의 자손을 루트로 하는 서브트리들은 오직 정점u를 통해 연결되고 각 서브트리끼리는 서로 연결되어 있지 않는다. 그렇기 때문에 각 서브트리가 u의 선조와 역방향으로 연결되어 있지 않으면 u는 절단점으로 분류된다. 쉽게말해 u의 자손들이 모두 역방향 간선을 통해 u의 선조로 올라갈 수 있다면 u는 절단점이 아니다. 그리고 u가 스패닝 트리의 루트일 경우 u아래에 자손이 하나뿐이거나 자손이 존재하지 않는다면 u는 절단점이 아니게 된다.
무향 그래프에서 절단점을 포함하지 않는 서브그래프를 이중 결합 컴포넌트라고 부른다. 그러므로 이중 결함 컴포넌트에서 임의의 한 점을 지우더라도 정점간의 연결유무는 변하지 않는다.
코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>> adj;
// -1로 초기화 해야된다.
vector<int> discovered;
vector<bool> isCutVertex;
int counter;
int findCutVertex(int here, int isRoot) {
discovered[here] = counter++;
int ret = discovered[here];
int children = 0;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i];
if (discovered[there] == -1) {
++children;
int subTree = findCutVertex(there, false);
if (isRoot && subTree >= discovered[here])
isCutVertex[here] = true;
ret = min(ret, subTree);
}
else
ret = min(ret, discovered[i]);
}
if (isRoot)
isCutVertex[here] = (children >= 2);
return ret;
}다리찾기
절단점을 찾는 문제와 비슷한것으로 그래프에서 다리를 찾는 것이 있다. 이때 다리는 어떤 간선을 삭제했을 때 이 간선을 포함하던 컴포넌트가 두개의 컴포넌트로 쪼개지는 간선이다.
무방향그래프에서 간선은 3가지(트리간선, 순방향간선, 역방향간선) 종류가 있었다. 간선(u, v)가 순방향 간선이라고 해보자. 순방향 간선은 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 의미하며 순방햔 간선보다 트리간선이 먼저 생성된다. 그러므로 순방향 간선이 존재한다는 것은 u부터 v까지 가는 경로가 존재한다는 것을 의미한다. 그러므로 (u,v)가 순방향 간선일 때 (u,v)를 삭제한다 하더라도 컴포넌트는 두 개로 나누어 지지 않는다. 무방향 그래프에서는 순방향이나 역방향이 구분되지 않기 때문에 역방향도 비슷한 맥락으로 이해하면 된다. 그러므로 트리 간선들 중 특정한 간선만 다리가 될 수 있다.
트리 간선 (u, v)가 다리가 되기 위해서는 v를 루트로 하는 서브트리와 v보다 위에 있는 정점들과 연결된 간선이 오직 (u, v)여야 된다. 따라서 역방향 간선 중 자신의 부모로 가는 간선을 무시하도록 한 뒤, v와 그 자손들에서 역방향 간선으로 닿을 수 있는 정저므이 최소 발견 순서가 u후라면 (u, v)가 다리라고 판정할 수 있다
