백준 No.11266 [단절점]

BOJ No.11266 [단절점]

---

  문제 

11266번: 단절점 (acmicpc.net)

11266번: 단절점

---

  설명 

 <알고리즘 분류> 
 * 그래프
 * 단절점

 

 단절점 
: 어떠한 그래프에서 임의의 정점을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 정점

  개념 자체는 간단하다. 위 그래프에서 단절점은 3, 5 번째 정점이 될 것이다. 3번 정점을 제거함으로써 3개의 그래프로 나뉘어지고, 5번 정점을 제거함으로써 2개의 그래프로 나뉘어졌기 때문이다.

 

  단절점에 대한 파악은 루트노드부터 깊이 우선 탐색으로 정점들을 방문하면서, 그 때 가지는 방문 순서를 기준으로 파악한다.

 

 

  1번째 정점을 루트노드라고 할 때 방문 깊이 우선 탐색(DFS) 를 통한 노드들의 방문순서는 위와 같이 정의할 수 있다. 보면 단절점인 3, 5 번째 정점을 보면 공통적인 특성이 있다. 단절점들은 바로 다음 방문되는 정점부터 DFS를 진행했을 때 해당 단절점의 방문 순서보다 이르게 방문이 된 정점을 만나지 않는다. 단절점으로 하여금 이전에 방문이 되었던 정점들과 이후에 방문이 될 정점들이 각각의 그래프를 형성하게 되는 것 이다.

  그렇다면 단절점이 아닌 2번 정점은? 다음으로 방문되는 정점들 중 4번 정점이 2번 정점보다 이전에 방문한 1번 정점을 만나는 것을 확인할 수 있다. 고로 2번 정점은 단절점이 아니다.

 

  여기서 주의깊게 여겨야 할 요소가 있다. 바로 루트노드 이다. 루트노드는 모든 정점들 중 가장 먼저 방문이 된 정점이므로 위와 같은 특성을 이용해 단절점 여부를 파악할 수 없다.위 공식을 루트노드에 적용하면 루트노드는 항상 단절점이 되기 때문이다. 루트노드는 자식 그룹의 개수가 2개 이상이면 단절점으로 여긴다. 아래 루트노드 (1번 정점) 은 자식 그룹을 3개 가지고 있으므로 단절점에 해당한다.

  문제에서 두 정점이 연결이 된 양방향 간선들에 대한 정보를 준다. 그 정보들을 통해 위와 같이 그래프를 만든 후 위와 같은 특성과 DFS 알고리즘을 통해 단절점들을 파악할 수 있다.

 

 <정리> 
1. 루트노드가 자식 정점들의 그룹을 2개 이상 가지고 있다면 루트노드는 단절점이다.
2. 루트 노드가 아닌 모든 노드들은 방문 순서를 통해 단절점 여부를 파악한다.
   2-1. 단절점 여부를 파악하려는 정점 바로 다음 정점부터 탐색되는 정점들이 파악하려는 정점보다 이전에 방문된 정점과 만난 적이 있다면 이 점은 단절점이 아니다.
   2-2. 단절점 여부를 파악하려는 정점 바로 다음 정점부터 탐색되는 정점들 모두 파악하려는 정점 보다 같거나 큰 방문 순서를 가지고 있다면? 이 점은 단절점이다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100000

using namespace std;

priority_queue<int, vector<int>, greater<int>> ans;
vector<vector<int>> adj;
vector<int> visitCount;
vector<bool> ansCount;
int v, e;
int cnt = 1;

int dfs(int curVer, bool isRoot, int parent) {
	visitCount[curVer] = cnt++;

	int minVisit = visitCount[curVer];
	int childCount = 0;
	int low = MAX;

	for (auto curChild : adj[curVer]) {
		if (curChild == parent) continue;
										
		if (visitCount[curChild] == 0) {
			childCount++;	

			low = dfs(curChild, false, curVer);

			if (!isRoot && low >= visitCount[curVer]) {
				if (!ansCount[curVer]) {		
					ans.push(curVer);
					ansCount[curVer] = true;
				}
			}

			minVisit = min(minVisit, low);
		}
		else minVisit = min(minVisit, visitCount[curChild]);
	}

	if (isRoot && 2 <= childCount) {
		if (!ansCount[curVer]) {
			ans.push(curVer);
			ansCount[curVer] = true;
		}
	}

	return minVisit;
}

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

	cin >> v >> e;
	adj.resize(v + 1);
	ansCount.assign(v + 1, false);
	visitCount.assign(v + 1, 0);

	for (int i = 1; i <= e; i++) {
		int a, b; cin >> a >> b;

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

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

	cout << ans.size() << '\n';

	while (!ans.empty()) {
		cout << ans.top() << ' ';
		ans.pop();
	}
}