백준 9466번 텀 프로젝트 C++

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

 

이미 방문한 노드도 다음에 또 방문해야하는 경우가 있다. 그 경우를 잘 처리해줘야한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

int n;
int g_cnt = 0;
vector<int> graph;
vector<bool> visited;
unordered_set<int> us;

void Dfs2(int start, int curr) {
    g_cnt++;
    int next = graph[curr];
    if (next == start) return;
    Dfs2(start, next);
}

void Dfs(int start, int curr) {
    if (visited[curr]) {
        for (auto a : us) {
            visited[a] = true;
        }
        return;
    }
    auto it = us.find(curr);
    if (it == us.end()) {
        us.insert(curr);
    }
    else {
        for (auto a : us) {
            visited[a] = true;
        }
        Dfs2(curr, curr);
        return;
    }
    int next = graph[curr];
    Dfs(start, next);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        g_cnt = 0;
        graph = vector<int>(n + 1);
        visited = vector<bool>(n + 1, false);
        for (int i = 1; i <= n; i++) {
            cin >> graph[i];
        }
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            us.clear();
            Dfs(i, i);
        }
        cout << n - g_cnt << "\n";
    }
}