[백준 11266] 단절점

문제 링크 => 11266번: 단절점 (acmicpc.net)

11266번: 단절점

---

DFS 트리를 이용하여 단절점을 찾아내는 문제이다.

 

Tarjan's Algorithm 을 이용하여 노드별로 dfs로 방문하면서 매겨지는 dfn값과 해당 노드에서 최소 dfn 값 (low)을 찾는 과정 속에서 단절점을 찾아내는 방법은 다음과 같다.

 

case 1. 자식노드가 dfn 값이 매겨지지 않은 경우 : dfn[cur] <= low[child] 이면서 현재 노드의 부모 노드가 존재하는 경우 현재 노드는 단절점이다.

 

case 2. 부모 노드가 없는 루트 노드의 자식 노드의 갯수가 2개 이상인 경우 해당 루트 노드는 단절점이다.

 

위 2개의 경우를 다음과 같은 예시를 통해 dfn, low 값을 매겨가면서 단절점을 찾아보도록 하자.

 

이러한 connected graph 가 있다고 가정하자.

 

이 그래프를 dfs를 통해 얻어지는 각 노드의 dfn, low 값은 다음과 같이 얻게 된다.

 

(0) 1 : low[1] = dfn[1] = 1 이고 루트 노드 1과 이어진 정점으로 이동

(1) 1 => 2 : low[2] = dfn[2] = 2

(2) 2 => 3 : low[3] = dfn[3] = 3 

(3) 3 => 1 : dfn[3] > dfn[1] 이므로 low[3] = min(low[3], dfn[1]) = 1 으로 update

(4) 3 => 4 : low[4] = dfn[4] = 4

(5) 4 => 2 : dfn[4] > dfn[2] 이므로 low[4] = min(low[4], dfn[2]) = 2 으로 update

(6) 4 => 5 : low[5] = dfn[5] = 5

(7) 5 => 6 : low[6] = dfn[6] = 6 

(8) 6 => 7 : low[7] = dfn[7] = 7

(9) 7 => 5 : dfn[7] > dfn[5] 이므로 low[7] = min(low[7], dfn[5]) = 5 으로 update

(10) 6 => 7 부분에서 low[6] = min(low[6], low[7]) = 5 으로 update

(11) 5 => 6 부분에서 low[5] = min(low[5], low[6]) = 5 으로 update 

(12) 2 => 3 부분에서 low[2] = min(low[2], low[3]) = 1 으로 update

 

생략한 부분이 약간 있지만 대략 이런식으로 dfs가 이뤄지면서 dfn, low 값이 매겨짐을 확인할 수 있다.

 

여기서 case 1 에서의 조건을 통해서 단절점을 찾아본다면 4번 노드와 5번 노드이다.

 

4번 노드인 경우에 4 => 5 로 dfs를 하면서 5번 노드가 최종적으로 얻어진 low 값과 비교한다면 dfn[4] = 4 <= low[5] = 5 를 만족하고 4번 노드는 부모 노드인 3번 노드를 가지고 있으므로 단절점이다.

 

5번 노드인 경우에 5 => 6 로 dfs를 하면서 6번 노드가 최종적으로 얻어진 low 값과 비교한다면 dfn[5] = 5 <= low[6] = 5 를 만족하고 5번 노드는 부모 노드인 4번 노드를 가지고 있으므로 단절점이다.

 

그렇다면 case 2 에서의 조건을 통해 단절점을 찾아본다면 존재하지 않는다.

 

루트 노드인 1번 노드가 1 => 2 => 3 이런식으로 방문을 함으로써 1 => 3 으로 갈 경우 dfn[3] 값이 이미 매겨졌으므로 자식 노드의 갯수가 1개밖에 존재하지 않는다.

 

따라서 다음과 같이 빨간색 원으로 된 부분이 단절점이 된다.

 

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v[10001];
int low[10001], dfn[10001], child[10001];
int V, E, nodeNum;
bool ac[10001];

void input() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void dfs(int x, int mp = -1) {
	dfn[x] = low[x] = ++nodeNum;

	for (int y : v[x]) {
		if (y == mp) continue; // 부모로 가는 간선 무시
		if (!dfn[y]) { // 방문하지 않은 경우
			child[x]++;
			dfs(y, x);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				if (mp != -1) ac[x] = true; // 부모가 존재하는 경우
			}
		}
		else if (dfn[x] > dfn[y]) { // 조상으로 올라가는 경우
			low[x] = min(low[x], dfn[y]);
		}
	}

	if (mp == -1 && child[x] >= 2) ac[x] = true; // 루트노드의 자식이 2 이상인 경우
}

void solve() {

	for (int i = 1; i <= V; i++) {
		if (!dfn[i]) dfs(i);
	}

	int cnt = 0;
	for (int i = 1; i <= V; i++) {
		if (ac[i]) cnt++;
	}

	cout << cnt << endl;
	for (int i = 1; i <= V; i++) {
		if (ac[i]) cout << i << " ";
	}

}

int main() {

	input();
	solve();

	return 0;
}