[알고리즘 BFS & DFS 10] TEAMPROJECT

문제

---

이번 가을학기에 '문제 해결' 강의를 수강하는 학생들은 팀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 같은 팀의 팀원으로 구성된 한 팀도 허락된다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 같이하고 싶은 학생 딱 한 명을 선택해야 한다. 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

과목을 수강한 학생 수가 1명이고, 그 한 명이 자기 자신을 선택하는 경우. 혹은, 학생 수가 N명이고, 1번 학생이 2번 학생을 선택하고, 2번 학생이 3번 학생을 선택하고,..., N-1번 학생이 N번 학생을 선택하고, N번 학생이 1번 학생을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 수업에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해, (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

입력

---

첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

 

출력

---

첫 줄에 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

예제 입력 1

7

3 1 3 7 3 4 6

예제 출력 1

3

예제 입력 2

8

1 2 3 4 5 6 7 8

예제 출력 2

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//백준 9466번
 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;
 
const int MAX = 100005;
int arr[MAX];
int check[MAX]={0,};
int temp[MAX] = {0,};
 
//입력
int n;
 
void DFS(int node){
  //현재 순번 = node
  //현재 순번이 바라보고 있는 다음 node = noWnode;
  int nowNode = arr[node];
  
  check[node]++;
  
  //만약 현재 순번과 현재 순번이 바라보고 있는 노드가 같다면...
  if(nowNode == node){
    check[node] = 2;
    return;
  }
  
  //다른 노드를 바라보고 있다면...
  if(check[nowNode] == 0 || check[nowNode] ==1){
    DFS(nowNode);
  }else if(check[nowNode] == -1){
    //다음 노드가 순환이 없는 -1 이라면
    check[node] = -1;
  }
  
  //순환이라면..
  if(check[node]==2) return;
  else{
    check[node] = -1;
    return;
  }
}
 
 
int main(){
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int cnt;
  cin>>cnt;
  for(int i=0; i<cnt; i++){
    memset(arr,0,sizeof(arr));
    memset(check,0,sizeof(check));
  
  cin>>n;
  for(int i=1; i<=n; i++){
    cin>>arr[i];
  }
  
  
  for(int i=1; i<=n; i++){
    if(check[i] == 0){
      DFS(i);
    }
  }
 
  int cnt = 0;
  for(int i=1; i<=n; i++){
    if(check[i]==-1){
      cnt++;
    }
  }
  cout<<cnt<<endl;
  }
  
  return 0;
}