백준 11266번 단절점

< 백준 11266번 단절점 - 마포 코딩박>

사용한 알고리즘: DFS


 단절점을 구하는 문제였습니다.
 A번 노드가 Root가 아니고, 자식노드들이 A번을 통하지 않고는 위의 노드로 갈 수 없다면 A번 노드는 단절점 입니다. 만약 A번 노드가 Root 라면 자식트리가 2개 이상이면 단절점입니다.
 SCC, BCC 구현으로 풀 수도 있지만, DFS 만으로도 풀 수 있는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 46~51)
 DFS로 모든 노드를 둘러볼 것입니다. 아직 방문하지 않은 노드가 있다면 DFS 를 시작하고, 해당 노드가 그 노드가 포함된 component의 Root 라고 생각합니다.

(2) (코드 11~36)
 DFS 를 시작할 시, 노드(이하 curr) 의 dfsn, 즉 번호를 붙여줍니다.
 DFS는 curr 에서 올라갈 수 있는 최대한 작은 번호(이하 ret) 를 return 해 줄 것입니다.
 curr 와 연결된 노드들을 둘러보며 ret 을 최신화해줍니다. 방법은 다음과 같습니다.
 1. 연결된 노드가 이미 방문됐으면, 그 점의 dfsn을 받습니다. ( 이는 curr 이 자신보다 위의 노드와 연결됐음을 의미합니다. )
 2. 아직 방문하지 않은 노드라면, 새로운 자식'트리' 가 생기는 것입니다. 해당 연결노드는 root가 아님을 표시하고 DFS를 돌려 얻은 값을 받습니다.
 3. curr이 root가 아니고, 자식트리의 return값이 dfsn[curr] 보다 크거나 같다면 curr은 단절점입니다. ( 이는 curr의 자식트리가 curr 위의 노드로 갈 수 없다는 것을 의미합니다. ) 
 4. curr이 root 이고, 자식트리가 2개 이상이라면 curr은 단절점입니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 100000;
	int V, E, df;
	vector<int> adj[MAX+2];
	// 각 노드의 번호
	int dfsn[MAX+2];
	// 단절점들 저장
	set<int> ans;
	int DFS(int curr, bool isitroot){
	dfsn[curr] = df;
	df++;
	// 올라갈 수 있는 최대 dfsn
	int ret = dfsn[curr];
	// 자식'트리' 수
	int CT = 0;
	for(auto child: adj[curr]){
	if(dfsn[child]!=0)
	ret = min(ret, dfsn[child]);
	// 자식트리 DFS
	else{
	CT++;
	int Ctree = DFS(child,false);
	// 자신이 root가 아니고, 자식트리가 자신 위로 가지 못하면
	if(Ctree>=dfsn[curr] && !isitroot)
	ans.insert(curr);
	// 올라갈 수 있는 최대 dfsn 업데이트
	ret = min(ret,Ctree);
	}
	}
	// 자신이 root 고 자식트리가 2개 이상 이면
	if(isitroot && CT>=2)
	ans.insert(curr);
	return ret;
	}
	int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> V >> E;
	for (int i = 0; i < E; ++i){
	int a, b;
	cin >> a >> b;
	adj[a].push_back(b);
	adj[b].push_back(a);
	}
	// 각 노드마다 번호 붙일꺼임. 시작은 1로
	df = 1;
	for(int i=1; i<=V; ++i){
	// isitroot=true : i 가 root 이다.
	if(dfsn[i]==0) DFS(i,true);
	}
	cout << ans.size() << '\n';
	for(auto ss: ans)
	cout << ss << ' ';
	return 0;
	}

view raw BOJ 11266.cpp hosted with ❤ by GitHub