[백준 C++] 6543 그래프의 싱크

문제

방향 그래프 G = (V, E)가 주어져 있다.

임의의 노드 u, v ∈ V에 대해서 u에서 v로 E에 포함된 간선만을 이용해 갈 수 있는 경로가 있으면 u→v로 표현한다.

만약 어떤 노드 v ∈ V가 자신으로부터 도달할 수 있는 모든 노드로부터 돌아오는 경로가 있다면, 즉 다음 조건을 만족한다면 노드 v ∈ V를 싱크라고 부른다.

• 조건: ∀w ∈ V, (v→w) ⇒ (w→v)

또한, 그래프 G의 싱크를 모아놓은 집합을 bottom(G)로 표현한다.

• bottom(G) = {v ∈ V: ∀w ∈ V, (v→w) ⇒ (w→v)}
  주어진 그래프 G=(V, E)의 bottom(G)를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫 줄에는 노드의 수 n (1 ≤ n ≤ 5,000)과 음이 아닌 정수 m (0 ≤ m ≤ 100,000)이 주어진다. V = {1, 2, ..., n}이고, 간선의 수 |E|=m임을 의미한다.

그 다음부터는 각 간선을 나타내는 m쌍의 수 v1 w1 v2 w2 ... vm wm이 공백으로 구분되어 주어진다. 이는 (vi, wi) ∈ E를 의미한다.

마지막 줄에 0이 주어지고, 이 경우는 처리하지 않고 프로그램을 종료시켜야 한다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다.

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

풀이

Bottom(G)란
그래프를 모두 SCC로 분류한뒤,
하나의 SCC내부의 모든 정점이 다른 SCC로 연결되지않았을때의 SCC내부 모든 정점의 집합이다.
이러한 SCC는 여럿이 존재 할 수 있다.

이것이 무엇인가 하믄 첫번째 테스트케이스는 아래와 같다.
빨간색, 파란색 두개의 SCC가 있을때, 파란색 -> 빨간색은 가능하나
빨간색SCC는 다음 SCC로 나아갈 수 없다.
이때 빨간색 SCC의 모든 정점이 Bottom(G)의 부분집합인것이다.

두번째 테스트케이스는 아래와 같다.
이또한 파란색SCC만 다음 SCC로 연결되있지 않다.
따라서 파란색SCC의 요소인 2번이 Bottom(G)의 부분집합이다.

또 아래와 같은 그래프가 있다고 치자.
이것을 SCC로 분류하면 아래와 같아진다.
여기서 하나의 SCC에서 다음 SCC로 나아가는 간선이 없는 것은

아래와 같다.
이 SCC들에 속한 정점들이 Bottom(G)인것이다.

이것을 코드로 나타내보자.

1. DFS 코드여기서 group은 각 정점이 어느 SCC그룹에 속하지는 기록하는 용도이다. 물론 기록되면 탐색을 마쳤고 당연히 SCC로 분류됬다는 의미 이므로
   101번 라인의 조건문으로 사용가능하다.(탐색을 마쳤고 아직 SCC로 분류되지 않은 점 y)
   
   
   
2. Bottom(G)를 구하는 과정. <= res에 결과를 담는다.
   모든 SCC그룹을 탐색하며
   각그룹마다 내부 구성 요소들이 연결된 모든 경로를 탐색한다.
   여기서 다른 SCC구성원과 연결되있으면 hasOutDegree를 false로 두어 다음 SCC그룹을 탐색하도록한다.
   위 과정에서 다른 SCC와 연결이 되지않은경우 res에 추가한다. 우리가 찾고자하는 Bottom이니까.

이러고나서 res를 오름차순 정렬후 출력하면된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
#define MAX 5001
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int N, M;
vi edge[MAX];
int idx, P[MAX];
int group[MAX];
si S;
vector<vi> SCC;

int DFS(int x);
void func();

int DFS(int x) {
	P[x] = ++idx;
	S.ph(x);

	int parent = P[x];
	rep(i, sz(edge[x])) {
		int y = edge[x][i];
		if (P[y] == 0)
			parent = min(parent, DFS(y));
		else if (!group[y])
			parent = min(parent, P[y]);
	}

	if (parent == P[x]) {
		vi scc;
		while (x) {
			int y = S.TT();
			S.PP();
			group[y] = sz(SCC) + 1; //SCC번호를 매김
			scc.pb(y);
			if (y == x) br;
		}
		SCC.pb(scc);
	}

	rt parent;
}

//프로그램 메인 로직
void func() {
	while (1) {
		//입력
		sc("%d", &N);
		if (N == 0) rt; //0을 입력받으면 종료
		sc("%d", &M);
		rep(_, M) {
			int v, w;
			sc("%d%d", &v, &w);
			edge[v].pb(w);
		}

		//SCC생성
		rrep(i, 1, N + 1)
			if (P[i] == 0) DFS(i);

		//SCC내부의 모든 정점이 다른 SCC로 이어지는 연결이 없다면
		//해당 SCC내부의 모든 정점을 결과 res에 저장
		//res벡터는 outDegree = 0 인 정점들의 집합이다.
		vi res;
		rep(i, sz(SCC)) {
			bool hasOutDegree = true;
			rep(j, sz(SCC[i])) {
				if (!hasOutDegree) br;
				int x = SCC[i][j];

				rep(k, sz(edge[x])) {
					int y = edge[x][k];
					if (group[x] != group[y])
						hasOutDegree = false;
				}
			}

			if (hasOutDegree)
				rep(j, sz(SCC[i]))
					res.pb(SCC[i][j]);
		}

		sort(all(res)); //정렬해달래

		//출력
		rep(i, sz(res))
			pr("%d ", res[i]); 
		pr("\n");

		//초기화
		idx = 0;
		SCC.cls();
		rrep(i, 1, N + 1) {
			edge[i].cls();
			P[i] = 0;
			group[i] = 0;
		}
	}
}

int main(void) {
	func();

	rt 0;
}