즉흥 여행 (Hard) (백준 26157)

안녕하세요. 오늘은 즉흥 여행을 떠날거예요.

문제

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

아이디어

이 문제는 SCC로 풀 수 있습니다.
SCC로 만든 그래프를 위상정렬 했을 때 두 갈래로 나누어지지만 않으면 됩니다. 즉, 위상정렬을 쭉 할 때 큐에 원소가 두개 이상 있으면 안됩니다.

소스코드

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

vector <int> v1[202020], v2[202020]; //정방향, 역방향
bool visited[202020] = { 0 };
stack <int> s;
vector <int> scc;
int idx = 0;


void dfs1(int node)
{
	visited[node] = true;
	for (int next : v1[node])
		if (visited[next] == false)
			dfs1(next);
	s.push(node);
}
void dfs2(int node)
{
	visited[node] = true;
	scc.push_back(node);
	for (int next : v2[node])
		if (visited[next] == false)
			dfs2(next);
}

vector <int> topologic_edge[202020];
int indegree[202020] = { 0 }, indegree2[202020] = { 0 };
int GroupNum[202020] = { 0 };
bool able(void)
{
	queue <int> q;
	for (int i = 1; i <= idx; i++)
	{
		indegree2[i] = indegree[i]; //임시저장
		if (indegree[i] == 0)
			q.push(i);
	}

	while (q.size())
	{
		if (q.size() > 1) //2이상이 되면
			return false;

		int now = q.front();
		q.pop();
		for (int next : topologic_edge[now])
		{
			indegree2[next]--;
			if (indegree2[next] == 0)
				q.push(next);
		}
	}
	return true;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, i, a, b;
	cin >> N >> M;
	for (i = 0; i < M; i++)
	{
		cin >> a >> b;
		v1[a].push_back(b);
		v2[b].push_back(a);
	}
	for (i = 1; i <= N; i++)
		if (visited[i] == false)
			dfs1(i);
	for (i = 1; i <= N; i++) visited[i] = false;

	while (s.size())
	{
		int node = s.top();
		s.pop();
		if (visited[node]) continue;
		dfs2(node);
		idx++;
		for (int now : scc)
			GroupNum[now] = idx; //그룹번호 부여
		scc.clear();
	}

	for (i = 1; i <= N; i++)
	{
		int from = i;
		for (int to : v1[from])
		{
			if (GroupNum[from] != GroupNum[to])
			{
				indegree[GroupNum[to]]++;
				topologic_edge[GroupNum[from]].push_back(GroupNum[to]);
			}
		}
	}

	if (able())
	{
		int cnt = 0;
		for (i = 1; i <= N; i++)
			if (indegree[GroupNum[i]] == 0)
				cnt++;
		cout << cnt << "\n";
		for (i = 1; i <= N; i++)
			if (indegree[GroupNum[i]] == 0)
				cout << i << ' ';
	}
	else cout << 0;
}

감사합니다.