[백준] 11266 단절점 + BCC 이중 연결 요소

문제

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

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

입력

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

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

출력

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

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

 

 

이중연결요소 Biconnected Component 문제입니다.

이중연결요소는 기본적으로 무향그래프에서 여러개의 정점을 묶어놓은 그룹을 의미하는데,

그 그룹안에서 정점 하나를 지워도 다른 정점들이 모두 연결되어있습니다.

 

따라서 여러 그룹 안에 하나의 정점이 동시에 존재할 수 있습니다.

그 여러 그룹에 존재하는 정점을 단절점이라 합니다.

 

BCC를 구하는 알고리즘은 SCC와 유사합니다.

하지만 차이점으로 SCC는 정점을 기본으로 분리하지만

간선을 이용해 BCC를 분리합니다.

기본적으로 DFS를 사용합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int V, E, dfsn[10001], cnt;
stack<pi>st;
vi adj[10001];
vvi bcc;
//pre는 부모노드를 의미합니다.
int dfs(int k,int pre=-1) {

	//result는 도달가능한 정점의 최소 dfsn을 저장합니다.
	int result = dfsn[k] = ++cnt;

	//모든 도달가능한 정점에대해
	for (int next : adj[k]) {

		//부모노드라면 생략
		if (next == pre)continue;

		//만약 처음 방문하는 간선이라면 stack에 Push
		if (dfsn[k] > dfsn[next])st.push(pi{ k,next });

		//이미 방문한 정점이라면, dfsn값을 비교하여 result에 작은값을 저장합니다
		if (dfsn[next] > 0)result = min(result, dfsn[next]);

		//처음 방문한 정점이라면 dfs로 진행합니다
		else {

			//result와 자식정점의 dfsn와 비교해 작은값을 저장합니다.
			int temp = dfs(next, k);
			result = min(result, temp);

			//만약 현재 dfsn과 자식 dfsn을 비교했을때, 현재값이 크거나 같으면
			//현재노드의 부모노드로는 더이상 갈 수 없음을 의미합니다. BCC를 발견했습니다.
			//현재노드까지 BCC입니다.
			if (temp >= dfsn[k]) {
				vi vt;
				while (!st.empty()) {
					pi top = st.top();
					st.pop();
					vt.push_back(top.first);
					vt.push_back(top.second);
					if (top == pi{ k,next })break;
				}
				bcc.push_back(vt);
			}
		}
	}
	return result;
}
int main() {
	FAST;
	cin >> V >> E;
	while (E--) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	rep(i, V) {
		if (dfsn[i] == 0) {
			dfs(i);
		}
	}
	vi ans;
	int v[10001];
	mset(v);
	bool u = false;
	for (auto r : bcc) {
		sort(r.begin(), r.end());
		r.erase(unique(r.begin(), r.end()), r.end());
		for (auto k : r) {
			if (v[k])ans.push_back(k);
			v[k] = 1;
		}
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	cout << ans.size() << "\n";
	for (auto r : ans) {
		cout << r << " ";
	}
}