[백준 11400] 단절선 (C++)

문제 링크: https://www.acmicpc.net/problem/11400

11400번: 단절선

1. 주의할 점

- 단절점/단절선의 원리를 알고 있어야 한다

- 단절점과 다르게 Root Node의 Child수를 몰라도 되며, 해당 Node의 Root가 어떤 Node인지 알아야 한다

 

2. 구현

- 모든 간선에 대한 정보를 V[] 벡터에 담는다

- DFS(현재 Node, Root Node번호)함수를 통해 단절선을 우선순위큐에 저장한다

- 단절점을 구할때와 달리 Child를 구하지 않아도 된다

- 현재 Node와 연결된 모든 간선을 검사하지만, 부모 Node와 연결된 간선은 검사하지 않는다

- 간선에 연결된 다른 Node에서 구한 Ret값이 현재 Node의 Check[]값보다 크다면(같은 경우는 계산하지 않는다) 단절선이므로 우선순위큐에 추가한다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[100001];
struct info {
	int start, dest;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.start == b.start)
			return a.dest > b.dest;
		return a.start > b.start;
	}
};
info tmp;
priority_queue<info, vector<info>, cmp> pq;
int check[100001];
int node, edge, s, e, cnt;

int dfs(int here, int root) {
	check[here] = ++cnt;
	int ret = check[here];
	for (int i = 0; i < v[here].size(); i++) {
		int next = v[here][i];
		if (root == next) continue;
		if (check[next]) {
			ret = min(ret, check[next]);
			continue;
		}
		int prev = dfs(next, here);
		if (prev >= check[here]) {
			tmp.start = min(here, next);
			tmp.dest = max(here, next);
			pq.push(tmp);
		}
		ret = min(ret, prev);
	}	
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}
	for (int i = 1; i <= node; i++) 
		if (check[i] == 0) 
			dfs(i, 0);
	cout << pq.size() << '\n';
	while (!pq.empty()) {
		int cs = pq.top().start;
		int cd = pq.top().dest;
		pq.pop();
		cout << cs << " " << cd << '\n';
	}
	system("pause");
	return 0;
}