사이클 크기 구하기 (텀 프로젝트)

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

DFS(Depth First Search) 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제.

기존의 vist 배열과 함께, 해당원소 탐색이 완료되었다는 done 배열을 이용하여 사이클 크기를 구하는문제.

 

#include <iostream>

using namespace std;
int point[100001];
bool vist[100001];
bool done[100001];
int TC , N , sum ;
void DFS(int Num ){
    vist[Num] = true;
    int next = point[Num];
    if(! vist[next] ) {
        DFS(next);
    }
    else{
        if(! done[next] ){ // = if(vist[next] == true  && !done[next])
            int cnt = 1;
            int n = point[Num]; // 현재 검사하고 있는 위치의 사이클 크기  
            while (true){
                if(n == Num) break;
                n = point[n];
                cnt ++ ;
            }
            sum += cnt;
        }
    }
    done[Num] = true; 
}
void init(){
    sum = 0;
    for(int i = 1 ; i <= N ;i++){
        vist[i] = false;
        done[i] = false;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> TC;
   
    for(int tc = 0; tc < TC; tc++){
        cin >> N;
        init();
        for(int i = 1; i <= N ; i++){
            cin >> point[i];
        }
        for(int i = 1; i <= N ; i++){
            if(vist[i] == false) DFS(i);
        }
        cout << N - sum <<endl;
    }
    return 0;
}