[BOJ] 백준 9466 텀 프로젝트

문제 링크

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

풀이

방향성 있는 그래프가 만들어집니다.

1) indgree가 0인 모든 배열을 큐에 넣어줍니다.

2) 위상 정렬을 돌립니다.

3) 어떤 팀에 속한다는 말은 곧 그래프에서 사이클을 이룬다는 말과 같습니다.

위상 정렬이 끝난 뒤 방문하지 못한 정점이 있다면, 그 정점은 사이클을 이룬다는 뜻입니다.

 

그러므로 위상 정렬 과정 중 방문한 정점의 개수를 출력해주면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int p[111'111], indeg[111'111];
int n;

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        memset(indeg, 0, sizeof(indeg));
        for (int i = 1; i < n + 1; i++) {
            cin >> p[i];
            indeg[p[i]]++;
        }
        queue<int> q;
        for (int i = 1; i < n + 1; i++) {
            if (indeg[i] == 0) q.push(i);
        }
        int ans = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            ans++;
            int next = p[now];
            if (--indeg[next] == 0)q.push(next);
        }
        cout << ans << '\n';
    }
}