(BOJ) 2152 여행 계획 세우기

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

 

문제 풀이:

scc로 묶어서 간선 만듦

시작점과 끝점의 scc가 같으면 그 scc의 개수 출력

다르면 bfs돌려서 출력

 

소스 코드:

int n, m,s,k, p[10001],scc[10001],dist[10001];
bool visit[10001];
vector<vector<int>> adj,adj2,scc_adj;
stack<int> st;
void dfs(int v) {
	visit[v] = true;
	for (int i : adj[v]) {
		if (visit[i]) continue;
		dfs(i);
	}
	st.push(v);
}
void rdfs(int v, int t) {
	visit[v] = true;
	p[v] = t;
	scc[t]++;
	for (int i : adj2[v]) {
		if (visit[i]) {
			if (p[i] != p[v]) {
				scc_adj[p[i]].push_back(p[v]); 
			}
			continue;
		}
		else rdfs(i,t);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m>>s>>k;

	adj.resize(n + 1);
	adj2.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w;
		cin >> q >> w;
		adj[q].push_back(w);
		adj2[w].push_back(q);
	}
	
	for (int i = 1; i <= n; i++) {
		if (visit[i]) continue;
		dfs(i);
	}
	memset(visit, false, sizeof(visit));

	int tmp = 0;
	while (!st.empty()) {
		int cur = st.top();
		st.pop();

		if (visit[cur]) continue;
		scc_adj.resize(++tmp);
		rdfs(cur, tmp - 1);
	}
	if (p[s] == p[k]) {
		cout << scc[p[s]] << '\n';
	}
	else {
		dist[p[s]] = scc[p[s]];
		queue<int> q;
		q.push(p[s]);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			if (cur == p[k]) continue;
			for (int i : scc_adj[cur]) {
				if (dist[i] < dist[cur] + scc[i]) {
					dist[i] = dist[cur] + scc[i];
					q.push(i);
				}
			}
		}
		cout << dist[p[k]] << '\n';
	}

	return 0;
}