백준 No.11400 [단절선]

BOJ No.11400 [단절선]

---

  문제 

11400번: 단절선 (acmicpc.net)

11400번: 단절선

---

  설명 

 <알고리즘 분류> 
 * 그래프
 * 단절선

 

 단절선 
: 어떠한 그래프에서 임의의 간선을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 간선

 

  [단절점]과  거의 비슷하게 생각을 하면 된다. 하지만 간선을 제거하는 경우는 단절점과 같이 정점을 제거하는 경우와 조금 다르게 다뤄지는 부분이 있다.

 

1. 단절선을 찾는 알고리즘은 단절점을 찾는 알고리즘과는 달리 루트노드를 특별하게 작업하지 않는다.

   - 루트노드가 단절점인지 파악을 할 때는 루트노드를 따로 검사를 하였지만, 단절선 여부를 파악할 땐 루트노드와 다른 노드들을 모두 동일한 노드로 취급하여 검사한다.

 

2. 현재 정점에서 DFS를 했을 때 현재 정점과 만나게 된다면 {현재 정점} --- {자식 정점} 은 단절선이 아니다.

   - 단절점에서는 어떠한 정점의 다음으로 방문되는 정점들은 현재 정점과 만나도 그 점은 단절점으로 취급을 하였다. 하지만 단절선에서는 자식 정점을 다음으로 있는 DFS 과정에서 현재 정점과는 만나면 단절선이 되지 못한다. 현재 정점과 만난다면 자식 정점이 간선을 계속해서 타고 오면서 결국 현재 정점과 연결된 루트가 있는 것 이기 때문이다.

  위 그래프에서 DFS를 하면서 2번 정점 다음으로 4번 정점을 방문한다고 할 때, 4번 정점 다음으로 방문되는 정점들은 모두 2번 정점보다 방문 순서가 이후이다. 따라서 {2}---{4} 간선은 단절선이 된다.

 

  하지만 4번 정점 다음으로 5번 정점을 방문한다고 할 때, 5번 정점 다음으로 방문이 되는 정점 중 4번 정점이 존재하므로, {4}---{5} 간선은 단절선이 되지 않는다.

 

 <정리> 
1. 단절점과 달리 루트노드를 구분하지 않는다.
2. DFS 과정에서 임의의 A 정점 다음으로 방문되는 정점들은 모두 A 정점보다 방문 순서가 늦은 정점들로만 구성이 되어있어야 A 정점과 다음으로 방문된 정점 사이의 간선이 단절선이 된다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100000

using namespace std;
typedef pair<int, int> pii;

struct comp {
	bool operator()(pii a, pii b) {
		if (a.first != b.first) return a.first > b.first;
		else return a.second > b.second;
	}
};

priority_queue<pii, vector<pii>, comp> pq;
vector<int> adj[MAX + 1];
int visitCount[MAX + 1];
bool dan[MAX + 1];
int v, e;
int cnt = 1;

int dfs(int curVer, int parVer) {
	visitCount[curVer] = cnt++;

	int minVisit = visitCount[curVer];
	int low = MAX;

	for (auto curChild : adj[curVer]) {
		if (curChild == parVer) continue;

		if (visitCount[curChild] == 0) {
			low = dfs(curChild, curVer);

			if (low > visitCount[curVer])
				pq.push({ min(curVer, curChild), max(curVer, curChild) });

			minVisit = min(minVisit, low);
			
		} else minVisit = min(minVisit, visitCount[curChild]);
	}
	return minVisit;
}

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

	cin >> v >> e;

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

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

	dfs(1, 0);
	cout << pq.size() << '\n';
	while (!pq.empty()) {
		cout << pq.top().first << ' ' << pq.top().second << '\n';
		pq.pop();
	}
}