단절점

단절점 (Articulation Points / Cut Vertices)

https://www.acmicpc.net/problem/11266

무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두개 이상의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점

단절점 찾기

어떤 정점 a와 a에 연결된 정점 b에 대해서
a가 시작정점인 경우

• 2 ≤ childA ⇒ A는 단절점
• 2 > childA ⇒ A는 단절점 X

a가 시작정점이 아닌 경우

• orderA ≤ lowB ⇒ A는 단절점
• orderA > lowB ⇒ A는 단절점

(orderV : 정점 V의 방문순서
lowV : 정점 V의 low → V 이후에 방문하는 정점들 중 V를 거치지 않고 방문 가능한 정점들의 order 중 가장 작은 값
childV : 정점 V의 자식 트리 수)

구현

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

int searchOrder;
vector<vector<int>> adjList;
vector<int> order;
vector<bool> isAp;

int dfs(int cur, bool isRoot) {
	order[cur] = searchOrder++;
	int low = order[cur];
	int child = 0;

	for (int next : adjList[cur]) {
		if (order[next] == 0) {
			child++;

			int subTreeLow = dfs(next, false);
			if (!isRoot && order[cur] <= subTreeLow) {
				isAp[cur] = true;
			}

			low = min(low, subTreeLow);
		}
		else {
			low = min(low, order[next]);
		}
	}

	if (isRoot && child >= 2) {
		isAp[cur] = true;
	}

	return low;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int v, e;
	cin >> v >> e;

	adjList.resize(v + 1);
	order.resize(v + 1, 0);
	isAp.resize(v + 1, false);

	while (e--) {
		int a, b;
		cin >> a >> b;

		adjList[a].push_back(b);
		adjList[b].push_back(a);
	}

	searchOrder = 1;
	for (int i = 1; i <= v; i++) {
		if (order[i] == 0) {
			dfs(i, true);
		}
	}

	return 0;
}