[BOJ 11400 // C++] 단절선

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11400번 문제인 단절선이다.
문제는 아래 링크를 확인하자.

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

11400번: 단절선

주어진 그래프의 단절선을 찾는 문제이다.

 

단절선(bridge; cut edge)이란 해당 에지를 지웠을 때 그래프의 component의 개수가 증가하는 에지이다.

 

각 노드에 대하여 방문순서를 매기며 dfs를 진행하고, 각 노드에서 자기 부모를 잇는 간선을 제외한 경로로 자신의 방문순서보다 빠른 방문순서를 가진 노드로 이동할 수 없다면 자신과 자기 부모를 잇는 에지를 단절선이라 판단하자.

 

위와 같이 판단할 수 있는 이유는 자신의 방문순서보다 빠른 방문순서를 가진 노드들은 전부 연결되어있기 때문이다.

 

문제에서 주어진 그래프가 연결그래프가 아닐 수 있음에 유의하여 구현하자.

 

아래는 제출한 소스코드이다.

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

vector<pair<int, int>> ans;

int V, E;
vector<int> G[100001];
int dfi[100001];
int dfidx = 1;
int dfs(int cur, int par) {
	int ret = dfi[cur] = dfidx++;
	for (auto node : G[cur]) {
		if (node == par) continue;
		if (dfi[node]) ret = min(ret, dfi[node]);
		else ret = min(ret, dfs(node, cur));
	}
	if (ret == dfi[cur] && par > 0) {
		if (cur < par) ans.emplace_back(make_pair(cur, par));
		else ans.emplace_back(make_pair(par, cur));
	}

	return ret;
}

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

	cin >> V >> E;
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int i = 1; i <= V; i++) {
		if (dfi[i] == 0) dfs(i, 0);
	}

	sort(ans.begin(), ans.end());
	
	cout << ans.size() << '\n';
	for (auto p : ans) {
		cout << p.first << ' ' << p.second << '\n';
	}
}