문제 간략 설명

각 학생이 프로젝트를 함께하고 싶은 학생을 정확히 한 명 선택한다. 팀을 이루려면 선택들이 순환을 형성해야 한다(자신을 선택하는 경우 포함). 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산한다.

풀이 방법

  1. 위상정렬과 비슷한 방식. 진입 차수가 0인 학생을 queue에 삽입.
  2. queue가 빌 때까지 빼면서 그 학생이 가리키고 있는 학생의 진입 차수를 감소시키고 0이 되면 queue에 삽입한다.
  3. queue에서 제거한 숫자만큼 출력 (사이클에 포함 안 됨)

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int T, N, cnt;

vector<int> students(100001);
vector<int> counts(100001, 0);
queue<int> q;

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

	cin >> T;

	while (T) {
		int cnt = 0;

		cin >> N;

		fill(counts.begin(), counts.end(), 0);

		for (int i = 1; i <= N; i++) {
			cin >> students[i];
			counts[students[i]]++;
		}

		for (int i = 1; i <= N; i++)
			if (counts[i] == 0)
				q.push(i);

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

			cnt++;

			if (--counts[students[n]] == 0)
				q.push(students[n]);
		
			q.pop();
		}

		cout << cnt << endl;

		T--;
	}

	return 0;
}

Key Points

Notepad