#10451 순열 사이클
https://www.acmicpc.net/problem/10451
단방향 그래프이다. map[i].push_back(a); map[a].push_back(i);를 둘 다 해주지 않아도 된다는 말이다 !!!
연결요소 개수를 구하는 문제(https://www.acmicpc.net/problem/11724)를 풀었다면 어렵지 않게 풀린다
#include <iostream>
#include <vector>
#include <string.h>
#define MAX 1001
using namespace std;
int n, m, a;
vector<int>map[MAX];
bool visited[MAX];
void dfs(int v) {
visited[v] = true;
for (int i = 0; i < map[v].size(); i++) {
if (!visited[map[v][i]]) {
dfs(map[v][i]);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T,count=0;
cin >> T;
for(int t=0;t<T;t++) {
memset(visited, 0, sizeof(visited));
cin >> m;
for (int i = 1; i <= m; i++) map[i].clear();
for (int i = 1; i <=m; i++) {
cin >> a;
map[i].push_back(a);
}
count = 0;
for (int i = 1; i <= m; i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
cout << count<<'\n';
}
}