[BOJ/Platinum 5] 백준 11400 단절선(C++)

문제 링크

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

11400번: 단절선

 

문제

그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

그래프의 정점은 1부터 V까지 자연수이다.

출력

첫째 줄에 단절선의 개수 K를 출력한다.

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

예제 입력 1

7 8
1 4
4 5
5 1
1 6
6 7
2 7
7 3
2 3

예제 출력 1

2
1 6
6 7

알고리즘 분류

• 그래프 탐색

풀이

그래프에서 어떤 정점이 단절선이 되는 조건은 다음과 같다.

현재 정점의 방문 순서가 아직 방문하지 않은 자식 정점의 순서보다 빨라, 현재 간선을 거치지 않고서는 순서가 빠른 모든 정점에 도달할 수 없다면 현재 간선은 단절선이 된다.

DFS를 통하여 정점들의 방문 순서를 기록하면서, 현재 정점과 자식 정점의 방문 순서를 비교해서 현재 간선이 단절선이 될 수 있는지를 파악한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int V, E;
vector<int> Edge[MAX];
int visited[MAX];
vector<pair<int, int> > answer;

int DFS(int Parent, int Start, int Order) {
	int res = Order;
	visited[Start] = Order; // DFS 탐색 순서 지정

	for (int i = 0; i < Edge[Start].size(); i++) {
		int Next = Edge[Start][i]; // 다음 정점
		if (Parent == Next) {
			continue;
		}
		if (visited[Next] == 0) { // 다음 정점이 아직 탐색되지 않은 정점일 때
			int Next_Order = DFS(Start, Next, Order + 1); // 다음 정점의 방문 번호를 찾고
			if (Next_Order > visited[Start]) {
				/*
					현재 정점에서, 아직 방문하지 않은 정점의 방문 순서가 현재 정점의 순서보다 뒤라면
					현재 Edge는 단절선이 된다.(visited[Next] > visited[Start])
				*/
				answer.push_back(make_pair(min(Start, Next), max(Start, Next)));
			}
			res = min(res, Next_Order);
		}
		else {
			res = min(res, visited[Next]);
			continue;
		}
	}

	return res;
}

void Input() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int A, B;
		cin >> A >> B;
		Edge[A].push_back(B);
		Edge[B].push_back(A);
	}
}

void Settings() {
	for (int i = 1; i <= V; i++) {
		sort(Edge[i].begin(), Edge[i].end());
	}
	for (int i = 1; i <= V; i++) {
		if (visited[i] == 0) {
			DFS(0, i, 1);
		}
	}
}

void Find_Answer() {
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int i = 0; i < answer.size(); i++) {
		int S = answer[i].first;
		int E = answer[i].second;
		cout << S << " " << E << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}