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

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

9466번: 텀 프로젝트

문제

문제 해결

사이클을 이루는 팀원들이 한 팀이 된다. => 사이클이 이루어지고 있는 과정은 dfs를 통해 파악한다.

 

이 문제에서 포인트는 '사이클을 다 돌았다면?' 에 대한 해답을 찾는 것이다.

- 이미 방문한 정점을 다시 방문하면 사이클이 형성된다.

   - 여기서 시간복잡도가 커질 수 있다.. 이미 사이클이 형성된 학생은 다시 사이클인지 아닌지 체크해줄 필요가 없다. 그래서 이미 사이클이 형성된 학생인 것을 체크해줘야한다.

 

이렇게 나온 bfs 코드는 다음과 같다.

 

 

#include <iostream>
#include <cstring>

using namespace std;


bool visited[100001];
bool hasCycle[100001];
int partner[100001];
int cnt;

void dfs(int k) {
    visited[k] = true;

    int next = partner[k];

    if (!visited[next]) {
        dfs(next);
    } else if (!hasCycle[next]) {
        for (int i = next; i != k; i = partner[i]) {
            cnt++;
        }
        cnt++;
    }
    hasCycle[k] = true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {

        int N;
        cin >> N;

        memset(visited, false, N+1);
        memset(hasCycle, false, N+1);

        for (int j = 1; j <= N; j++) {
            cin >> partner[j];
        }
        for (int k = 1; k <= N; k++) {
            if (!visited[k]) {
                dfs(k);
            }
        }
        cout << N - cnt << "\n";
        cnt = 0;
    }
    return 0;
}