백준 11400번 단절선

< 백준 11400번 단절선 - 마포 코딩박 >

사용한 알고리즘: DFS


 단절선을 구하는 문제입니다. DFS 한번 도는거 만으로 풀 수 있습니다.

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

(1) (코드 47~52)
 양방향 간선이므로 정점 a, b가 연결되어 있으면, 각 정점의 자식노드로 다른 정점을 저장합니다.

(2) (코드 15~39, 53~55)
 아직 방문하지 않은 정점을 DFS 로 돌릴 것입니다.
 Root 노드에서 자식노드를 다시 DFS로 돌려가면서 노드별로 번호(dfsn)를 매겨줍니다.
 DFS를 재귀적으로 돌릴 때 바로 직전에서 온 노드로는 돌아보지 않습니다.
 자식 노드가 자신의 번호(dfsn) 이상을 갈 수 없는 경우 해당 자식과의 간선이 단절선입니다.

	#include <iostream>
	#include <utility>
	#include <set>
	#include <algorithm>
	#include <vector>
	using namespace std;
	typedef pair<int, int> pii;
	const int MAX = 100000;
	int V, E, dfsn[MAX+1];
	vector<int> adj[MAX+1];
	// 단절선
	set<pii> ans;
	int cnt = 1;
	int DFS(int curr, int justbefore){
	dfsn[curr] = cnt;
	cnt++;
	// 올라갈 수 있는 최대 dfsn
	int ret = dfsn[curr];
	for(auto child: adj[curr]){
	// 바로 직전에서 온 노드는 돌아보자 않는다.
	if(child==justbefore) continue;
	if(dfsn[child]){
	ret = min(ret, dfsn[child]);
	continue;
	}
	int prev = DFS(child, curr);
	// justbefore 로 직전 노드로 가는 길이 없으니 prev = dfsn[curr] 인 경우 cycle 이 생긴거
	if(prev > dfsn[curr]){
	int a = min(curr,child);
	int b = max(curr,child);
	if(!ans.count(pii(a,b)))
	ans.insert(pii(a,b));
	}
	ret = min(ret,prev);
	}
	return ret;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> V >> E;
	if(V==1){
	cout << 0 << '\n';
	return 0;
	}
	for(int i=0; i<E; ++i){
	int a, b;
	cin >> a >> b;
	adj[a].push_back(b);
	adj[b].push_back(a);
	}
	// root 의 justbefore 은 0으로 하자
	for(int i=1; i<=V; ++i)
	if(dfsn[i]==0) DFS(i,0);
	cout << ans.size() << '\n';
	for(auto x: ans)
	cout << x.first << ' ' << x.second << '\n';
	return 0;
	}

view raw BOJ 11400.cpp hosted with ❤ by GitHub