문제 링크 https://www.acmicpc.net/problem/4013 풀이 SCC, 유니온 파인드, 위상 정렬, dp를 이용하여 풀이하였다. 다 푼 후에 다른 사람의 코드를 보고 깨달았지만, 유니온 파인드는 굳이 사용하지 않아도 된다. 출발지점부터 순회하며 dp를 돌리면 될 것 같지만 사이클이 존재하기 때문에 그럴 수 없다. 그렇기 때문에 사이클이 없는 방향 그래프로 바꿔줘야 한다. 사이클을 제거하기 위해 SCC를 사용한다. 아래 코드는 코사라주 알고리즘을 이용하였다. 구해진 SCC를 이용하여 사이클을 하나의 큰 노드로 합친다. 나는 이때 유니온 파인드를 사용하였다. 하지만 이미 SCC들을 모두 구했기 때문에 이미 합쳐져 있는 상태여서 유니온 파인드를 사용하지 않아도 된다. scc vector의 ..

풀이 위상 정렬을 이용하여 풀이할 수 있다. 위상 정렬을 이용하는 과정에서 더 쉬운 문제는 더 빨리 뽑기 위해 우선순위 큐를 이용하여 값이 작은 것을 우선으로 뽑아준다. 코드 #include #include #include using namespace std; int cnt[32003]; vector v[32003]; priority_queue q; // 작은 것부터 뽑음 int main() { int N, M; scanf("%d %d", &N, &M); while (M--) { int a, b; scanf("%d %d", &a, &b); v[a].push_back(b); cnt[b]++; } for (int i = 1; i

풀이 위상 정렬을 이용하여 풀이할 수 있다. 코드 #include #include #include using namespace std; int cnt[32003]; int main() { int N, M; scanf("%d %d", &N, &M); vector v(N + 1); while (M--) { int a, b; scanf("%d %d", &a, &b); v[a].push_back(b); cnt[b]++; } queue q; for (int i = 1; i