전화 돌리기

백준 24526번: 전화 돌리기

아이디어

그래프에서 사이클을 찾는다. 그 사이클에 포함된 노드와 사이클로 들어가는 노드를 제외한 노드가 몇 개 있는지 세주면 된다.

그래프를 거꾸로 뒤집는다. 그래도 사이클은 유지된다. 그리고 indegree를 기록하며 위상정렬을 한다. 사이클에 포함되고, 그 사이클에서 나가는 길에 포함된 노드 (원래는 그 사이클로 들어가는 노드) 는 indegree가 0이 아니라 방문하지 않을 것이다. 노드를 방문할 때마다 정답을 1씩 증가시키고 출력한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, M, indegree[100001];
vector<vector<int>> rev(100001);

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

    cin >> N >> M;
    while (M--) {
        int a, b;
        cin >> a >> b;
        rev[b].push_back(a);
        indegree[a]++;
    }

    queue<int> q;
    for (int i = 1; i < N+1; i++) {
        if (!indegree[i]) q.push(i);
    }

    int ans = q.size();

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

        for (int next : rev[cur]) {
            if (!--indegree[next]) {
                q.push(next);
                ans++;
            }
        }
    }
    
    cout << ans;

    return 0;
}

여담

대회때는 SCC로 묶어서 사이클 다 찾아야하나? 했는데 이런 간단한 풀이가 있었다니.. 연습 많이 해야겠다. 아 그리고 실행시간 내가 1등임.