백준[9466] - 텀 프로젝트

문제

백준 9466 문제 보기

접근 방법

시간 초과가 나기때문에 dfs를 돌지만 한 번 방문한 노드는 다시 방문하면 안된다. 한 번 방문을 체크할 때 사이클의 여부 역시 같이 판단해야한다. 사이클이 존재하면 사이클이 시작되는 노드를 저장하고 이후 계산을 통해 정답을 구한다.
1 시간 가량 계속 문제가 없는것 같았는데 ‘틀렸습니다’가 나와 삽질했지만 원인은 벡터를 다시 지워주지 않아서…

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int T, n, cnt;
int students[100001];
int visited[100001];
int cycle[100001];

vector<int> v;

void dfs(int node) {

    int next = students[node];
    if(!visited[next]) {
        visited[next] = 1;
        cycle[next] = 1;
        dfs(next);
        cycle[next] = 0;
    } else if(cycle[next] == 1) {
        v.push_back(next);
        cycle[next] = 0;
    }
}

void dfs2(int node) {

    int next = students[node];
    students[node] = -1;
    if(students[next] != -1)
        dfs2(next);
}

int main() {

    cin >> T;

    while(T--) {
        cin >> n;

        cnt = 0;
        v.clear();
        memset(visited, 0, sizeof(visited));
        memset(students, 0, sizeof(students));

        for(int i = 1; i <= n; i ++) {
            cin >> students[i];
        }

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

        auto size = static_cast<int>(v.size());

        for(int i = 0; i < size; i ++) {
            int node = v[i];

            dfs2(node);
        }

        for(int i = 1; i <= n; i ++) {
            if(students[i] != -1)
                cnt ++;
        }

        cout << cnt << '\n';
    }

    return 0;
}