[백준] 2152 여행 계획 세우기

문제

평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000)개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다.

태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.

도시와 비행로에 대한 정보가 주어졌을 때, S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하는 프로그램을 작성하시오. 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다. 물론 같은 도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다.

입력

첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공로가 존재함을 의미한다.

출력

첫째 줄에 방문할 수 있는 도시의 최대 개수를 출력한다. 만약 여행 계획을 목표대로 세울 수 없다면 0을 출력한다.

 

출발도시부터 도착도시에 도착할때까지, 간선은 여러번 이용가능하며 최대 얼마나 많은 도시를 방문할 수 있는지 묻는 문제입니다.

간선을 여러번 이용가능하기때문에, 정점(도시)간 이어진 간선이 사이클을 이룬다면 그 사이클에 도착만하면 사이클 안의 모든 도시를 방문할 수 있습니다.

따라서 scc로 구성된 단방향그래프 DAG를 그리고, DP를 이용하면 몇개의 SCC를 지날 수 있는지 구할 수 있고, 따라서 총 몇개의 도시를 지날 수 있는지 구할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;
int N, M, S, T, a, b, v[10001], dp[10001], s[10001], n[10001], cnt, num, m;
vector<int>adj[10001], adj2[10001], st;
int dfs(int k) {
	st.push_back(k);
	int parent = v[k] = ++cnt;
	for (auto r : adj[k]) {
		if (!v[r]) {
			parent = min(parent, dfs(r));
		}
		else if (!s[r]) {
			parent = min(parent, v[r]);
		}
	}
	if (parent == v[k]) {
		num++;
		while (1) {
			auto top = st.back();
			s[top] = num;
			n[num]++;
			st.pop_back();
			if (top == k)break;
		}
	}
	return parent;
}
void tarjan() {
	for (int i = 1; i <= N; i++)
		if (!v[i])dfs(i);
}

int dfs2(int k) {
	if (dp[k])return dp[k];

	for (auto r : adj2[k]) {
		auto c = dfs2(r);
		if (c)
			dp[k] = max(dp[k], n[k] + c);
	}

	return dp[k];
}

void solve() {
	
	for (int i = 1; i <= N; i++) {
		for (auto r : adj[i]) {
			if (s[i] != s[r]) {
				adj2[s[i]].push_back(s[r]);
			}
		}
		sort(adj2[s[i]].begin(), adj2[s[i]].end());
		adj2[s[i]].erase(unique(adj2[s[i]].begin(), adj2[s[i]].end()), adj2[s[i]].end());
	}
	dp[s[T]] = n[s[T]];
	dfs2(s[S]);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> S >> T;
	while (M--) {
		cin >> a >> b;
		adj[a].push_back(b);
	}
	tarjan();
	solve();
	cout << dp[s[S]];
}