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

10451번 : 순열 사이클

---

문제 )

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

 

 

 

출력 :

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

 

 

 

 

 

 

풀이)

테스트 케이스마다 dfs나 bfs를 돌려야하므로 vector를 clear()를 통해 초기화 시켜준 뒤 사용하였다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> vec;
vector<int> visited;
 
void dfs(int x)
{
    if (visited[x] == 1) return;
    visited[x] = 1;
 
    for (int i = 0; i < vec[x].size(); i++)
    {
        dfs(vec[x][i]);
    }
    
}
 
int main()
{
    // 속도 증가를 위함
    cin.tie(NULL);
    cout.tie(NULL);
    ::ios::sync_with_stdio(false);
 
    int t;
    cin >> t;
 
    int n;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
 
        // for문 돌때마다 vector 초기화
        vec.clear();
        vec.resize(n + 1);
        visited.clear();
        visited.resize(n + 1);
 
        // 단방향 간선이므로
        int num;
        for (int j = 1; j < n + 1; j++)
        {
            cin >> num;
            vec[j].push_back(num);
        }
 
        // 순열 사이클 탐색
        int count = 0;
        for (int j = 1; j < n + 1; j++)
        {
            if (visited[j] == 1) continue;
            dfs(j);
            count++;
        }
 
        cout << count << "\n";
 
    }
 
    return 0;
}
 

---

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

10451번: 순열 사이클