[Gold 3] 9466 텀 프로젝트

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

 

DFS를 사용해 순환하는 그래프인지 확인하는 것이다. 

입력을 통해 다음 노드를 알 수 있고

처음 DFS함수를 호출한 값으로 돌아가야 circle 형태가 된다.

 

따라서 next 값이 방문하지 않은 node인 경우 DFS를 수행하게 된다.

 

이미 이전에 방문한 노드인 경우

사이클을 형성하였는지 확인해야한다.

 

사이클 형성을 확인하는 방법은 done배열을 사용한다.

done값이 아직 false인 경우 사이클 확인 여부를 검사하지 않은 것이다.

따라서 자기 자신을 포함해 이동할 수 있는 모든 노드의 개수를 구하면 사이클인 노드의 개수를 구할 수 있다.

 

방문한 노드들은 done 배열에 true로 체크하여 사이클 여부를 확인하지 않도록 한다.

 

따라서 1번노드에서 1-> 3 -> 3으로 이동할 때

1 번 노드를 방문한 경우 3번 노드로 이동하게 된다.

이후 3번 노드에서는 3번 노드로 향하기 때문에 서클인지 확인하게 된다.

3번 노드는 3번 노드로 돌아가기 때문에 서클을 형성하게 되므로 answer 수를 1 증가시킨다.

 

이후, done[3]과 done[1]은 true가 되어 사이클 여부를 재확인 하지 않도록 한다.

 

#include <iostream>
#include <cstring>
using namespace std;

int T;
int n;
int graph[100001];
int answer = 0;
bool visited[100001];
bool done[100001];


void isCycle(int r){
    visited[r] = true;
    int next = graph[r];

    if(!visited[next])
        isCycle(next);
    else if(!done[next]){
        // 방문 했지만 아직 사이클이 아닌 경우
        // 자기 자신을 포함한 멤버들을 카운트
        int i = next;
        while(i != r){
            answer++;
            i = graph[i];
        }
        answer++;
    }
    done[r] = true;
}

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

    
    cin>>T;
    while(T--){
        cin>>n;
        int to;
        for(int i = 1;i<=n;i++){
            cin>>to;
            graph[i] = to;
        }
        answer = 0;
        memset(visited,false,sizeof(visited));
        memset(done, false, sizeof(done));

        for(int i = 1;i<=n;i++){
            if(!visited[i])
                isCycle(i);
        }

        cout<<n - answer<<'\n';
    }
}