10451_순열 싸이클

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

10451번: 순열 사이클

간선으로 연결된 정점들의 집합이 몇 개 있는지 구하는 문제이다. DFS나 BFS로 풀 수 있다. 흔히 영역을 구하는 문제와 비슷한 것 같다. 오늘은 간단하게 코드만 올리겠다. 

 

#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
int area[1001];
 
void dfs(int p, int flag, vector<int> g[1001]){
    if(area[p]) return;
    area[p] = flag;
    for(int i = 0; i < g[p].size();i++){
        dfs(g[p][i], flag, g);
    }
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
 
    cin >> t;
    while(t--){
        int n, v, flag;
        vector<int> g[1001];
 
        cin >> n;
        memset(area, 0, sizeof(area));
        for(int i = 1; i <= n; i++){
            cin >> v; g[i].push_back(v);
        }
        flag = 1;
        for(int i = 1; i <= n; i++){
            if(area[i]) continue;
            dfs(i, flag, g);
            flag++;
        }
        cout << flag - 1 << "\n";
    }
}