[백준/BOJ] 백준 24526번 : 전화 돌리기

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

24526번: 전화 돌리기

 

그래프에서 사이클에 포함되는 노드와, 사이클 쪽으로 이동하도록 연결된 노드들을 판별해야 한다. 즉, 사이클 판별과, 사이클에 들어가는 노드들도 판별해야 된다.

문제를 해결하기 위해, 그래프의 간선의 방향을 거꾸로 연결해서, 위상 정렬을 수행하여 위상 정렬의 큐에 들어가지 않는 노드들은 거꾸로 연결된 그래프에서 사이클에 속한 노드들이거나, 사이클에서 나가는 방향으로 연결된 노드들이라고 확인할 수 있다. 해당 노드들은 원래 그래프들에서 사이클인 노드들과, 사이클로 들어가는 노드들이므로, 이를 이용해 문제를 해결했다.

 

코드

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

int n, m;
vector<int> re_adj[100005]; //그래프를 거꾸로 뒤집어서 생각한다
vector<int> indegree(100005, 0);
vector<int> cycle(100005, 1); //사이클에 포함되는 번호거나, 사이클로 진입하는 번호일때

//그래프를 거꾸로 뒤집었으므로
//거꾸로 뒤집은 그래프의 사이클이나, 해당 사이클에서 나가는 노드들은 위상정렬 큐에 값으로 들어가지 않는다
//즉, 위상정렬을 하며 큐에 들어오지 않는 번호들이 제대로된 그래프에서 사이클이거나, 사이클로 들어가는 번호들이다
void check_cycle() {

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int here = q.front();
		q.pop();

		cycle[here] = 0;

		for (int i = 0; i < re_adj[here].size(); i++) {
			int there = re_adj[here][i];

			indegree[there]--;
			if (indegree[there] == 0) {
				q.push(there);
			}
		}
	}
}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		//그래프를 거꾸로 연결한다
		re_adj[v].push_back(u);
		indegree[u]++;
	}

	//사이클 판별
	check_cycle();

	int result = 0;
	for (int i = 1; i <= n; i++) {
		if (cycle[i] == 0) {
			result++;
		}
	}

	cout << result << "\n";

	return 0;
}