[BOJ/Platinum 4] 백준 11266 단절점(C++)

문제 링크

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

11266번: 단절점

 

문제

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

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

입력

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

입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. 정점은 1부터 V까지 번호가 매겨져 있다.

출력

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

둘째 줄에는 단절점의 번호를 공백으로 구분해 오름차순으로 출력한다.

예제 입력 1

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

예제 출력 1

3
1 6 7

알고리즘 분류

• 그래프 탐색

풀이

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

1. 현재 정점이 루트 정점일 때

  - 자식 정점이 2개 이상이라면 현재 정점은 단절점이 된다.

2. 현재 정점이 루트 정점이 아닐 때

  - 현재 정점보다 방문 순서가 뒤인 자식 정점들이 현재 정점을 거치지 않고 현재 정점보다 방문 순서가 앞인 정점들을 방문할 수 있다면 현재 정점은 단절점이 아니고, 방문하지 못 한다면 현재 정점은 단절점이 된다.

 

이제 저 조건들을 생각하면서 DFS를 사용하여 정점의 방문 순서를 매긴다. 

시작 정점을 Root로 여기고, 자식 정점들을 방문해 나간다. 먼저 현재 정점이 Root가 아닐 때를 따진다. 현재 노드의 특정 자식 정점이 이미 방문한 상태라면(visited[Next] > 0), 현재 정점의 방문 순서는 이미 기록해 두었던 현재 정점의 방문 순서와 자식 정점의 방문 순서 중 최솟값이 된다. 이렇게 해서 현재 정점에서 자식 정점들이 현재 정점을 거치지 않고 현재 정점보다 빠른 방문 번호를 가진 정점으로 갈 수 없는 경우를 찾을 수 있다. 자식 정점을 방문하지 않았다면(visited[Next] == 0), 자식 정점의 방문 순서를 다시 DFS를 사용하여 파악하고, 자식 정점의 방문 순서보다 현재 정점의 방문 순서가 더 빠르다면 현재 정점보다 방문 순서가 더 빠른 정점들로 자식 정점들이 현재 정점을 거치지 않고 이동할 수 없으므로, 현재 정점은 단절점이 된다. 

다음으로 현재 정점이 Root인 경우 자식 정점이 2개 이상이라면 현재 정점은 단절점이 된다.

 

방금 이해하고 쓴 거라 틀렸다면 지적 부탁드림.

코드

#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 10001
#define LL long long
#define INF 1e9

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

int DFS(int Parent, int Start, int Order, bool isRoot) {
	int res = Order;
	visited[Start] = Order; // DFS 탐색 순서 지정
	int Child = 0; // 자식 노드 수

	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, false); // 다음 정점의 방문 번호를 찾고
			Child++;
			if (!isRoot && (Next_Order >= visited[Start])) {
				/*
					현재 정점이 Root가 아니고, 현재 정점보다 빠른 방문 번호를 가진 정점으로 
					자식 정점들이 갈 수 없다면 현재 정점은 단절점이다. (visited[Next] >= visited[Start])
				*/
				answer[Start] = true;
			}
			res = min(res, Next_Order);
		}
		else { 
			/*
				다음 정점이 이미 DFS에서 탐색된 정점이라면(visited[Next] == true)
				현재 정점의 방문 순서와 탐색된 정점의 방문 순서 중 최솟값을 가진다.
				이렇게 해서 현재 정점에서 자식 정점들이 현재 정점을 거치지 않고
				현재 정점보다 빠른 방문 번호를 가진 정점으로 갈 수 없는 경우를 찾을 수 있다.
			*/
			res = min(res, visited[Next]);
		}
	}

	if (isRoot && (Child >= 2)) { // 그런데 현재 정점이 Root고, 자식 정점을 2개 이상 가진다면
		answer[Start] = true; // 현재 정점은 단절점이다.
	}

	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, true);
		}
	}
}

void Find_Answer() {
	int res = 0;
	for (int i = 1; i <= V; i++) {
		if (answer[i]) {
			res++;
		}
	}
	cout << res << "\n";
	for (int i = 1; i <= V; i++) {
		if (answer[i]) {
			cout << i << " ";
		}
	}
	cout << "\n";
}

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

	return 0;
}