[백준 11400] 단절선

문제 링크 => 11400번: 단절선 (acmicpc.net)

11400번: 단절선

---

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

 

[백준 11266] 단절점 :: M - J - C (tistory.com) 에서 단절점을 구하는 과정에서 Case 2 를 고려하지 않고 Case 1 에서 dfn[cur] < low[child] 을 만족하는 경우에 cur ~ child 로 이어진 간선은 단절선이다.

 

그리고 단절선을 구하고 주의해야 할점은 문제에서 단절선을 사전순으로 출력하라 했으므로 정렬을 잘 해주는 것이 중요하다.

(이 부분을 질문 검색을 살펴보면서 알게됨...)

 

풀이 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[100001];
vector<pair<int, int>> AC_Edge;
map<pair<int, int>, int> m;
int low[100001], dfn[100001];
int V, E, nodeNum;

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]) { // 방문하지 않은 경우
			dfs(y, x);
			low[x] = min(low[x], low[y]);
			if (dfn[x] < low[y]) { // 루트가 아닌 경우
				int X = min(x, y);
				int Y = max(x, y);
				if (!m[{X, Y}]) {
					m[{X, Y}] = 1;
					AC_Edge.push_back({ X,Y });
				}
			}
		}
		else if (dfn[x] > dfn[y]) { // 조상으로 올라가는 경우
			low[x] = min(low[x], dfn[y]);
		}
	}
}

bool compare(pair<int, int> x, pair<int, int> y) {
	if (x.first == y.first) {
		return x.second < y.second;
	}
	return x.first < y.first;
}

void solve() {

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

	sort(AC_Edge.begin(), AC_Edge.end(), compare);

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

}

int main() {

	input();
	solve();

	return 0;
}