백준 6543 그래프의 싱크

문제 URL : https://www.acmicpc.net/problem/6543

6543번: 그래프의 싱크

문제 접근법 : 

scc알고리즘 문제입니다.

bottom(G) 를 구하기위해선 scc안에서 outdegree가 없는

노드르 찾아야합니다.

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> adj,vscc;
vector<int> check,finish,st,outdegree,cscc;
int id=0;
int color=0;
void input(){
	cin>>n;
	if(n==0)exit(0);
	cin>>m;
	int a,b;
	adj = vector<vector<int>>(n+1);
	for(int i=0;i<m;i++){
		cin>>a>>b;
		adj[a].push_back(b);
	}
}
int scc(int cur){
	check[cur]=++id;
	int root = check[cur];
	st.push_back(cur);
	for(int next:adj[cur]){
		if(check[next]==0)root=min(root,scc(next));
		else if(!finish[next]) root= min(root,check[next]);
	}
	if(check[cur]==root){
		vector<int> v;
		while(true){
			int node = st.back();
			st.pop_back();
			v.push_back(node);
			finish[node]=1;
			cscc[node]=color;
			if(cur==node)break;
		}
		color++;
		vscc.push_back(v);
	}
	return root;
}
void solve(){
	id = color=0;
	vscc.clear();
	cscc = outdegree = check = finish=vector<int>(n+1);
	for(int i=1;i<=n;i++)if(check[i]==0)scc(i);
	
	for(int i=1;i<=n;i++){
		for(int next:adj[i]){
			if(cscc[i]!=cscc[next]){
				outdegree[cscc[i]]++;
			}
		}
	}
	vector<int>res;
	for(int i=0;i<color;i++){
		if(!outdegree[i]){
			for(int cur : vscc[i]){
				res.push_back(cur);
			}
		}
	}
	sort(res.begin(),res.end());
	for(int i:res)cout<<i<<" ";
	cout<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	while(true){
		input();
		solve();
	}
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.