[BOJ] 9466번 텀 프로젝트 c++

https://www.acmicpc.net/problem/9466

문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

---

입력 1
2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

출력 1
3
0

---

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

vector<int> v;
vector<bool> visited, group;
int cnt;

void dfs(int x) {
  int next = v[x];
  visited[x] = true;

  if(!visited[next]) {
    dfs(next);
  }
  else if(!group[next]) {
    for(int i = next; i != x; i = v[i])
      cnt++;
    cnt++;
  }

  group[x] = true;
}

int main() {
  int T;
  int n, tmp;

  scanf("%d", &T);

  for(int i = 0; i < T; i++) {
    scanf("%d", &n);

    v.resize(n + 1);
    visited.assign(n + 1, false);
    group.assign(n + 1, false);
    cnt = 0;

    for(int j = 1; j <= n; j++) {
      scanf("%d", &tmp);
      v[j] = tmp;
    }

    for(int j = 1; j <= n; j++) {
      if(!visited[j])
        dfs(j);
    }
    printf("%d\n", n - cnt);
  }
}

DFS를 이용해서 연결된 노드들이 사이클을 이루는지 확인하는 문제다. 처음에는 brute force로 풀어서 시간 초과가 나오길래 'group'이라는 벡터를 하나 더 만들어서 시간을 줄였다. DFS로 노드들을 탐색하다가 이미 방문했던 노드를 다시 방문한다면(방문했던 노드들 중에서 사이클이 존재한다는 의미이므로), 그 노드부터 시작해서 사이클을 이루는 노드들만 모두 카운트했다.