코드 복사/붙여넣기 하는 당신이 아름답습니다.

2152 : 여행 계획 세우기

풀이

주어진 그래프에서 scc를 구해서, 각 컴포넌트를 노드로 하는 새로운 그래프를 만들자

scc로 구성된 그래프는 항상 DAG이다

여기서 위상정렬 같은 느낌으로 dp? 같은 느낌으로 으쌰으쌰 하자

타잔으로 scc를 구하면 위상정렬의 역순으로 컴포넌트를 구하게 된다

아몰랑

코드

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
const int MAXN = 1e4 + 10;

int n, m, s, e;
int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN];
vi gph[MAXN];
vector<vi> res;

int dfs(int now) {
	chk[now] = ++cnt;
	int ret = chk[now];
	stk[pos++] = now;
	for (int nxt : gph[now]) {
		if (!chk[nxt]) ret = min(ret, dfs(nxt));
		else if (!scc[nxt]) ret = min(ret, chk[nxt]);
	}

	if (ret != chk[now]) return ret;

	res.push_back(vi());
	while (1) {
		int top = stk[--pos];
		scc[top] = res.size();
		res[scc[top] - 1].push_back(top);
		if (top == now) break;
	}

	return ret;
}

set<int> adj[MAXN];

int main() {
	scanf("%d %d %d %d", &n, &m, &s, &e);
	for (int i = 1; i <= m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		gph[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)
		if (!chk[i]) dfs(i);

    for (int i = 1; i <= n; i++) {
        for (int it : gph[i]) {
            if (scc[i] != scc[it]) {
                adj[scc[i]].insert(scc[it]);
            }
        }
    }

    vector<int> d(n+1);
    s = scc[s];
    e = scc[e];
    d[s] = res[s-1].size();
    for (int i = s; i >= e; i--) {
        for (int it : adj[i]) {
            d[it] = max(d[it], d[i]+(int)res[it-1].size());
        }
    }

    printf("%d\n", d[e]);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2019-05-19 23:39

Read more posts by this author