[BOJ 9466] 텀 프로젝트 (C++)

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

9466번: 텀 프로젝트

#include <bits/stdc++.h>

using namespace std;
int student[100001];
bool visited[100001];
bool group[100001];
int cnt;

void dfs(int x){
    visited[x]=true;
    int next=student[x];
    if (!visited[next]){
        dfs(next);
    }
    else if (!group[next]){     //방문 전에 했지만, 아직 결정되지 않은 애들(싸이클 발생!)
        for (int i=next; i!=x; i=student[i]){
            cnt++;
        }
        cnt++;
    }
    group[x]=true;
}

int main(){
    int T;
    vector<int> ans;
    cin>>T;
    while (T--){
        cnt=0;
        int n, x;
        cin>>n;
        for (int i=1; i<=n; i++){
            cin>>x;
            student[i]=x;
            visited[i]=false;
            group[i]=false;
        }
        for (int i=1; i<=n; i++){
            if (!visited[i]){
                dfs(i);
            }
        }
        ans.push_back(n-cnt);
    }
    for (int i=0; i<ans.size(); i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

3시간 동안 고민하고.. 시간초과 및 틀렸습니다 여러번 받고.. 결국 답 보고 푼 문제.

 

DFS+싸이클 찾는 문제이다.

 

이 문제의 핵심은 싸이클의 갯수인데, 싸이클은 방문했던 정점들을 다시 지났고 그 정점이 아직 group 여부가 결정이 안된 상태일 때 생성된다. 그 지점부터 싸이클을 이루는 정점이 몇개 있는지 계산한다.

 

방문을 나타내는 visited 배열/ group이 만들어졌거나 아예 만들어지지 않는 경우가 결정된 경우를 나타내는 group 배열을 이용한다.

 

방문하지 않았으면 방문하고

전에 방문했는데 그룹여부가 결정이 안된 애들이면 싸이클이므로 싸이클에 해당하는 애들의 갯수를 세준다.