[백준/BOJ] 백준 11400번 : 단절선

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

11400번: 단절선

 

BCC(이중 연결 요소, 이중 결합 요소), 단절선을 이용해서 문제를 해결했다.

 

코드

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

int v, e;
vector<int> adj[100005];
vector<int> visited(100005, 0);

vector<int> node_id(100005, 0);
int node_id_cnt = 0;

vector<pair<int, int>> result;

int dfs(int here, int before) {

	visited[here] = 1;

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	int ret = node_id[here];

	//BCC, 단절선을 이용해서 문제 해결
	//here을 루트 노드로 보고, 자식 노드(child)들을 dfs 했을때, 루트 노드보다 먼저 방문된 노드를 탐색하는지 확인
	for (int i = 0; i < adj[here].size(); i++) {

		int child = adj[here][i];

		//직전에 지난 노드(before)는 dfs하지 않는다 
		if (child == before) {
			continue;
		}

		//child노드를 탐색한적이 없을때
		if (visited[child] == 0) {

			//자식노드가 dfs를 통해 탐색한 노드 중 가장 작은 node_id
			int min_node_id = dfs(child, here);

			//min_node_id의 값이 node_id[here]보다 클때
			//즉 단절선이 될때
			if (node_id[here] < min_node_id) {
				result.push_back(make_pair(min(here, child), max(here, child)));
			}

			ret = min(ret, min_node_id);
		}

		else {
			ret = min(ret, node_id[child]);
		}
	}

	return ret;
}

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

	cin >> v >> e;

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

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

	dfs(1, -1);

	sort(result.begin(), result.end());

	cout << result.size() << "\n";
	for (int i = 0; i < result.size(); i++) {
		cout << result[i].first << " " << result[i].second << "\n";
	}

	return 0;
}