취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18133번 문제인 가톨릭대학교에 워터 슬라이드를??이다.
문제는 아래 링크를 확인하자.

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

주어진 문제의 상황을 건물을 노드로, 터널을 방향이 있는 에지로 보아 그래프로 모델링하자.

같은 SCC 내에 속한 노드들은 서로 방문했다가 다시 자기 자신으로 돌아올 수 있다는 성질이 있음을 상기하자. 이를 이용해 주어진 그래프의 각 SCC를 노드로 하는 condensation graph의 indegree가 0인 노드의 개수를 세는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> G[100001];
int dfi[100001];
int dfidx = 1;
int ndi[100001];
int ndidx = 1;

vector<int> stk;

int dfs(int cur) {
	stk.emplace_back(cur);
	int ret = dfi[cur] = dfidx++;
	for (auto& x : G[cur]) {
		if (dfi[x]) {
			if (!ndi[x]) ret = min(ret, dfi[x]);
		}
		else ret = min(ret, dfs(x));
	}

	if (dfi[cur] == ret) {
		while (stk.back() != cur) {
			ndi[stk.back()] = ndidx;
			stk.pop_back();
		}
		ndi[stk.back()] = ndidx++;
		stk.pop_back();
	}

	return ret;
}

int indegree[100001];
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	for (int n = 1; n <= N; n++) {
		if (!ndi[n]) dfs(n);
	}

	for (int cur = 1; cur <= N; cur++) {
		for (auto& nxt : G[cur]) {
			if (ndi[cur] != ndi[nxt]) indegree[ndi[nxt]]++;
		}
	}

	for (int i = 1; i < ndidx; i++) {
		if (!indegree[i]) ans++;
	}

	cout << ans;
}