[ BOJ 백준 6543번 - 그래프의 싱크 ] 해설 및 코드

https://www.acmicpc.net/problem/6543

목적

한 노드 a부터 출발하여 도달할 수 있는 모든 노드들에서 다시 a로 되돌아 올 수 있다면, a를 싱크 노드라고 한다. 이러한 싱크 노드들을 구하자. 

 

접근법

1. 그래프 이론 중, 방향 그래프에서 싱크 정점(sink vertex)이란 나가는 간선이 없는 정점(outdegree가 0)이다. (문제의 싱크 노드의 정의와는 다르다.) 만약에 여러 SCC로 이루어진 그래프에서 싱크 SCC가 있다면, 그걸 구하는 것이 이 문제의 목적일 것이다. 즉, 한 SCC에서 다른 SCC로 가는 길이 없는 SCC를 구하는 것이다.

 

2. 코사라주 알고리즘으로 SCC를 구하는 과정에서, 각 SCC에 번호를 매겨 각각의 정점들이 어떠한 SCC에 속해있는지에 대한 정보를 저장한다. 

 

3. 각 SCC의 노드들에서 다른 SCC로 가는 노드가 있는지 검사하며 bottom(G)를 구한다. 

 

#include<bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
 
const int MAXN=5001;
int n,s[MAXN], no;
bool vis[MAXN];
 
void dfs(int u, vvi &edge, vi &list){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])dfs(v, edge, list);
    list.push_back(u);
    s[u]=no;
}
 
bool isSink(int u, vvi &edge){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v]&&(s[u]!=s[v]||!isSink(v, edge)))return false;
    return true;
}
 
void findSink(vvi &scc, vvi &edge){
    vector<int> ans;
    memset(vis, false, n+1);
    for(vi &list:scc)if(isSink(list[0], edge))for(int &v:list)ans.push_back(v);
    
    sort(ans.begin(),ans.end());
    for(int &v:ans)cout<<v<<' ';
    cout<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    while(cin>>n && n){
        int m;cin>>m;
        
        vvi edge(n+1), redge(n+1);
        while(m--){
            int v,w;cin>>v>>w;
            edge[v].push_back(w);
            redge[w].push_back(v);
        }
        
        vector<int> order;
        memset(vis, false, n+1);
        for(int i=1;i<=n;++i)if(!vis[i])dfs(i,edge,order);
        
        vvi scc;
        no=0;
        memset(vis, false, n+1);
        for(int i=n-1;i>=0;--i)if(!vis[order[i]]){
            vi list;
            dfs(order[i],redge,list);
            scc.push_back(list);
            no++;
        }
        
        findSink(scc,edge);
    }
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.