[백준 10451번 C++] 순열 사이클

10451번: 순열 사이클 (acmicpc.net)

10451번: 순열 사이클

 

---

이해하기

바로 전 문제였던 [백준 11724번 - 연결요소의 개수]와 거의 동일하다.

다른 점이 있다면 방향이 있는 간선들로, 사이클의 개수를 구해야한다. 또, 테스트 케이스가 주어져서 여러 번 반복해야했다. 

 

코드는 거의 비슷한데 테스트 케이스를 위한 반복문과 배열/벡터 초기화 코드가 추가 되었고

순열을 저장할때 v[i].push_back(a)를 한번만 저장하면 됐다. (방향 그래프이므로)

 

-- 벡터를 초기화 하는 법 (clear)

vector<int> v[n];

for(int i=1; i<=n; i++){
       v[i].clear();
}

 

---

최종코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> v[1001];
int visited[1001]={0,};
int count = 0;

void dfs(int n){
    visited[n] = 1;
    for(int i=0; i<v[n].size(); i++) {
        int x = v[n][i];
        if(visited[x] == 0) dfs(x);
    }
}

int main()
{
    
    int T;
    cin >> T;
    
    int n;

    while(T--){
        int count = 0;
        cin >> n;
        
        //각각의 테스트 케이스에 대해 순열을 저장
        int a;
        for(int i=1; i<=n; i++){
            cin >> a;
            v[i].push_back(a);
        }
        
        for(int i=1; i<=n; i++){
            if(visited[i] == 0){
                dfs(i);
                count++;
            }
        }
        
        cout << count << "\n";
        
        //벡터, visited 배열 초기화 
        for(int i=1; i<=n; i++){
            v[i].clear();
            visited[i] = 0;
        }
    }
    
    return 0;
}