[백준/BOJ] 백준 2152번 : 여행 계획 세우기

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

2152번: 여행 계획 세우기

타잔 알고리즘을 이용해 강한 연결 요소(SCC)를 구하고 SCC들의 그래프를 만든 뒤, 알고리즘 분류에 위상 정렬이 있는 것을 이용해 위상 정렬을 통해 문제를 해결했다.

 

코드

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

int n, m, s, t;
vector<int> adj[10001];

//알고리즘 분류에 위상정렬 -> 위상정렬을 이용한 풀이법

//강한 연결 요소(SCC) 타잔 알고리즘 사용
vector<int> visited(10001, 0);
vector<int> node_id(10001, 0);
int node_id_cnt = 0;
vector<int> maked(10001, 0);
vector<int> node_scc_id(10001, 0); //[정점번호] = scc id
vector<int> scc_id_num(10001, 0); //[scc id] = 해당 scc에 속한 정점들의 개수
int scc_id_cnt = 0;
vector<int> scc_adj[10001];
stack<int> st;

//위상정렬 사용
vector<int> scc_indegree(10001, 0);
vector<int> scc_cache(10001, -1);
vector<int> discovered(10001, 0);
queue<int> q;

int Dfs(int here)
{
	visited[here] = 1;

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	st.push(here);

	int parent = node_id[here];

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

		if (visited[there] == 0)
		{
			parent = min(parent, Dfs(there));
		}

		else if (maked[there] == 0)
		{
			parent = min(parent, node_id[there]);
		}
	}

	//자기 자신이 기준이 될때
	if (parent == node_id[here])
	{
		scc_id_cnt++;

		while (1)
		{
			int st_top = st.top();
			st.pop();

			node_scc_id[st_top] = scc_id_cnt;
			maked[st_top] = 1; //scc가 만들어지는 정점 체크
			scc_id_num[scc_id_cnt]++;

			if (st_top == here)
				break;
		}
	}

	return parent;
}

//위상정렬 사용
int Solve(int start, int dest)
{
	for (int i = 1; i <= scc_id_cnt; i++)
	{
		if (scc_indegree[i] == 0)
			q.push(i);
	}

	//출발지점 부터 움직이는것
	discovered[start] = 1;
	scc_cache[start] = scc_id_num[start];

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

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

			//출발지점에서 시작한 경로일때
			if (discovered[here] == 1)
			{
				discovered[there] = 1;

				//출발지에서 시작한 경로중 처음인 위치 there일때
				if (scc_cache[there] == -1)
				{
					scc_cache[there] = scc_cache[here] + scc_id_num[there];
				}

				else
				{
					scc_cache[there] = max(scc_cache[there], scc_cache[here] + scc_id_num[there]);
				}
			}

			scc_indegree[there]--;

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

	}

	int ret;

	if (discovered[dest] == 0)
		ret = 0;

	else
		ret = scc_cache[dest];

	return ret;
}

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

	cin >> n >> m >> s >> t;

	for (int i = 0; i < m; i++)
	{
		int a, b;

		cin >> a >> b;
		adj[a].push_back(b);
	}

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			int here = i;
			int there = adj[i][j];

			//here과 there가 서로 다른 scc에 속할때
			if (node_scc_id[here] != node_scc_id[there])
			{
				scc_adj[node_scc_id[here]].push_back(node_scc_id[there]);
				scc_indegree[node_scc_id[there]]++;
			}
		}
	}

	cout << Solve(node_scc_id[s], node_scc_id[t]);

	return 0;
}