[백준] 9466. 텀 프로젝트(c++)

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

쉽지 않았다.

틀렸던 방식은 loop 마다 visited를 새로 생성해서 o(n^2)이 되어 시간초과가 나오는 문제였다.(방문했던 노드를 다시 한번 방문한다는...)

 

-> 이번 방문에서 자기 자신을 다시 만났을 경우, 사이클이라는 것을 표시해줄 -1을 넣어주고, 한 사이클을 돌았을 때 (-1을 다시 만났을 때) 탈출해주면 된다.

이미 지나갔었던 방문 배열을 만나게 된다면, 자연스럽게 사이클이 아니라는 것이니 break 해주면 된다.

 

---

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <limits.h>
#include <queue>
#include <set>
#include <math.h>
#include <stack>
#include <deque>

using namespace std;

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

    int t;

    cin >> t;

    while (t--) {
        int n;

        cin >> n;

        vector<int> arr(n + 1);
        vector<int> visited(n + 1);
        int ans = 0;

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

        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                int cur_v = i;

                while (1) {
                    visited[cur_v] = i;
                    cur_v = arr[cur_v];

                    // 이번 방문에서 지나간 학생에 도달했을 경우
                    if (visited[cur_v] == i) {
                        // 사이클에 들어갈 학생들
                        while (visited[cur_v] != -1) {
                            visited[cur_v] = -1;
                            cur_v = arr[cur_v];
                        }
                        break;
                    }
                    // 이전 방문에서 지나간 학생에 도달했을 때는 break
                    if (visited[cur_v] != 0) break;
                }
            }
        }

        for (int j = 1; j < n + 1; j++) {
            if (visited[j] != -1)
                ans++;
        }
        cout << ans << '\n';
    }

    return 0;
}