[BOJ/C++] 10451 순열 사이클 : DFS

문제

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

풀이

DFS 기본 형식은 똑같은데 인접리스트 만들 때, directed graph인데 undirected graph로 만들어서 삽질함 ;

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v[1001]; //인접 리스트
bool check[1001];


void dfs(int node) {
	check[node] = true;

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];
		
		if (!check[next]) {
			dfs(next);
		}
	}
}


int main() {
	int test_num;
	cin >> test_num;
	
	while(test_num--) {
		int N;
		int ans = 0;
		cin >> N;
		
		//전역변수 초기화
		fill_n(check, 1001, false);
		for (int i = 1; i <= N; i++) {
			v[i].clear();
		}

		for (int i = 1; i <= N; i++) {
			int target;
			cin >> target;
			v[i].push_back(target);
		}

		for (int i = 1; i <= N; i++) {
			if (!check[i]) {
				dfs(i);
				ans++;
			}
		}

		cout << ans << '\n';
	}

	return 0;
}