[boj] 백준 9466 텀 프로젝트 (c++) - DFS

[문제]

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

 

[풀이]

사이클을 이룰 경우 해당 팀이 만들어진다. 사이클을 이뤄서 팀에 포함된 학생들의 수를 센 후 전체 학생 수에서 빼주면 된다.

여기서 사용된 isFinished 배열은 사이클을 이룰 경우 이미 방문한 정점도 다시 방문할 수 있기 때문에 다시는 방문할 필요가 없는 정점임을 표시해주기 위해 필요하다. (예제에서 4 -> 7 -> 6 -> 4 와 같이)

방문하지 않은 정점들에 대해서만 dfs를 돌려서 최적화해주어야 시간초과가 발생하지 않는다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321

using namespace std;

int t;
bool visited[100001];
bool isFinished[100001];
int graph[100001];
int cnt;

void dfs(int i){
    visited[i] = true;
    int next = graph[i];
    if(!visited[next]){
        dfs(next);
    }
    else if(!isFinished[next]){ //사이클을 이룸
        for(int j=next; j!=i; j=graph[j]){
            cnt++;
        }
        cnt++;
    }
    isFinished[i] = true;
}

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

    cin >> t;
    while(t--){
        int n;

        cin >> n;

        for(int i=1; i<=n; i++){
            cin >> graph[i];
        }
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        cout << n-cnt << "\n";

        cnt = 0;
        memset(visited, false, sizeof(visited));
        memset(isFinished, false, sizeof(isFinished));
    }
}