[백준 11266] 단절점 (C++)

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

11266번: 단절점

1. 주의할 점

- 단절점에 대한 이론을 알고 있어야 한다

- 단절점이란 해당 점을 끊었을때 컴포넌트의 수가 증가하며, Root가 아닌 경우 단절점을 지나지 않고는 그보다 앞선 번호에 도달 할 수 없거나, Root인 경우 연결된 간선의 수가 2개 이상이면 무조건 단절점이다

 

2. 구현

- V[]벡터에 간선의 정보를 모두 저장한다

- DFS()를 통해 단절점을 구한다

- 각 Node마다 ++Cnt를 통해 Visit[]배열에 할당해준다

- 각 Node에 연결된 모든 간선에서 반대 간선의 Visit[]값이 0이 아닐경우 그 중 최소값을 Ret에 저장한다

- Visit[]값이 0일 경우, 자식의 수를 1 증가시키며 Prev 변수에 다음 Node의 최소 Ret를 저장한다

- Prev의 값이 기존 Node의 Visit[]값보다 크고, 기존 Node가 Root가 아닐 경우 단절점이다

- 모든 간선을 거친 후, 해당 Node가 Root이며 간선이 2개 이상 존재할 경우, 단절점이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int node, edge, s, e, cnt;
vector<int> v[10001], ans;
int visit[10001];
bool cut[10001] = { false, };

int dfs(int here, bool root) {
	visit[here] = ++cnt;
	int ret = visit[here];
	int child = 0;
	for (int i = 0; i < v[here].size(); i++) {
		int next = v[here][i];
		//이미 구한 경우, 어떤 최소 Node와 연결되어 있는지
		if (visit[next]) {
			ret = min(ret, visit[next]);
			continue;
		}
		child++;
		int prev = dfs(next, false);
		//Root가 아니며, 단절점인 경우
		if (!root && prev >= visit[here]) 
			cut[here] = true;
		ret = min(ret, prev);
	}
	//Root이며 Child가 2개 이상일 때
	if (root && child > 1) {
		cut[here] = true;
	}
	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 (!visit[i])
			dfs(i, true);
	for (int i = 1; i <= node; i++) {
		if (cut[i])
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	system("pause");
	return 0;
}