[백준 9466번] [DFS / Cycle] 팀 프로젝트

Approach

1개의 정점을 기준으로 1개의 outstream만 가능하므로, 각 component별로 사이클 1개와 해당 사이클을 구성하고 있는 정점을 지시하는 정점들로 구성되어 있을 수 밖에 없다.

 

기존에 방문 여부를 판단하기 위해서 visited배열을 이용했다면, 해당 노드를 완전히 방문했는지를 체크하기 위해서 finished 배열을 추가해주면 된다. 자세한 내용은 kks227님의 블로그를 참고해주면 된다.

https://m.blog.naver.com/kks227/220785731077

깊이 우선 탐색(Depth-First Search) (수정 2019-08-18)

finished 배열을 넣어, 사이클을 판단할 수 있다는 아이디어는 잘 기억해두도록 하자.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int visited[100001];
int finish[100001];
int n;
int result;
vector<int> v;

void dfs(int x){
    visited[x] = 1;
    int to = v[x];
    if(!visited[to]){
        dfs(to);
    }
    else{
        if(!finish[to]){
            for(int i = to; i != x; i = v[i]) result++;
            result++;
        }
    }
    finish[x] = 1; // x의 연결 상태가 완전히 종료
    return;
}

int main(void){
    fastio;
    int t;
    cin >> t;

    while(t--){
        memset(visited, 0, sizeof(visited));
        memset(finish, 0, sizeof(finish));
        v.clear();
        result = 0;
        
        cin >> n;
        v.push_back(0);
        for(int i = 0; i < n; i++){
            int t;
            cin >> t;
            v.push_back(t);
        }

        for(int i = 1; i <= n; i++){
            if(!visited[i]) dfs(i);
        }
    
        cout << n - result << "\n";
    }
    return 0;
}