백준 6543 그래프의 싱크

www.acmicpc.net/problem/6543

6543번: 그래프의 싱크

이 문제는 SCC를 활용할 수 있는 문제이며, 본 블로그 내의 SCC 관련 포스팅을 꼭 같이 참조하기 바란다. 

 

이 문제는 SCC를 찾기만 하는 게 아니다. SCC를 이루는 요소에서 다른 정점 어디라도 갈 수 있는데, 돌아오지 못한다면 답이 아니게 된다.

위의 그림은 이전 SCC포스팅에서 사용한 그림이다. 위와 같은 그래프에서는 1-2-3이 원래 SCC를 이루지만, 3에서 4와 5도 갈 수 있고, 4와 5에서는 1, 2, 3으로 갈 수 없기 때문에 1, 2, 3, 4 (4도 마찬가지)는 답이 아니게 된다. 오로지 5만 답이 된다. 5에서 출발하면 자기 자신은 도달했다고 정하는 것이다. 

while(!q.empty()){
	int curr=q.front();q.pop();
	for(int nx:graph[curr]){
		if(us.find(nx)==us.end()){
			flag=1;
			break;
		}
		if(!vis2[nx]){
			vis2[nx]=1;
			q.push(nx);
		}
	}
	if(flag)break;
}

위의 코드와 같이, 필자는 매 SCC를 한번씩 구할 때마다 SCC를 이루는 요소를 unordered_set 등과 같은 어떠한 집합에 담았고, SCC를 이루는 각 정점에서 BFS를 돌면서 그 집합에 포함되지 않은 정점에 도달하면 break를 거는 식으로 풀이하였다.

us는 unordered_set이며 scc를 이루는 정점들을 담는다. 

 

<주요 내용>

SCC, 강한 연결 요소, DFS, 집합

 

<코드>

#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
const int sz=5e3+1;
int n, m, a, b, num, numsRecord[sz];
vector<int> graph[sz], graph_inv[sz], sccGr;
vector<pair<int,int> > scc;
stack<pair<int,int> > nums;
bool vis[sz],vis2[sz],flag;
unordered_set<int> us;

void sccSolve(int node){
    if (!vis[node]){
        vis[node] = 1;
        for (int nx : graph[node])
            sccSolve(nx);
        nums.push(make_pair(num, node));
        numsRecord[node] = num;
        num++;
    }
}
void sccSolve2(pair<int, int> p){
    if (!vis[p.second]){
        vis[p.second]=1;
        us.insert(p.second);
        scc.push_back(p);
        for(int nx:graph_inv[p.second])sccSolve2(make_pair(numsRecord[nx], nx));
        return;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(1){
        cin >> n;
        if(!n)break;
        num = 0;
        fill(vis + 1, vis + 1 + n, 0);
        fill(numsRecord + 1, numsRecord + 1 + n, 0);
        scc.clear();
        sccGr.clear();
        for (int i = 1; i <= n; ++i){
            graph[i].clear();
            graph_inv[i].clear();
        }
        cin >> m;
        while (m--){
            cin>>a>>b;
            graph[a].push_back(b);
            graph_inv[b].push_back(a);
        }
        for(int i=1; i<=n;++i)sccSolve(i);
        fill(vis+1,vis+1+n, 0);
        while (!nums.empty()){
            auto currp = nums.top();nums.pop();flag=0;
            us.clear();
            sccSolve2(currp);
            int sccsz=(int)scc.size();
            if(!sccsz)continue;
            sort(scc.begin(),scc.end());
            fill(vis2+1,vis2+n,0);
            vis2[scc[sccsz-1].second]=1;
            queue<int>q;
            q.push(scc[sccsz-1].second);
            while(!q.empty()){
                int curr=q.front();q.pop();
                for(int nx:graph[curr]){
                    if(us.find(nx)==us.end()){
                        flag=1;
                        break;
                    }
                    if(!vis2[nx]){
                        vis2[nx]=1;
                        q.push(nx);
                    }
                }
                if(flag)break;
            }
            if(!flag)for(auto e:scc)sccGr.push_back(e.second);
            scc.clear();
        }
        // 묶음이 있고(크기 1초과) 최소 numCnt가 0이 아니면서
        //  다른 묶음으로 이어지는 경우도 존재
        sort(sccGr.begin(), sccGr.end());
        for(auto e:sccGr)cout<<e<<' ';
        cout<<endl;
    }
    return 0;
}