[Silver / 10451] 순열 사이클

문제 링크

---

🔷 분류

그래프 이론, 그래프 탐색, 순열 사이클 분할

✒️ 문제 설명

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 $\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 3& 2& 7& 8& 1& 4& 5& 6\end{array}\right)$ 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 $\left(\begin{array}{ccccc}1& \dots & i& \dots & n\\ {\pi }_1& \dots & {\pi }_i& \dots & {\pi }_n\end{array}\right)$ 로 나타냈다면, i에서 π_i로 간선을 이어 그래프로 만들 수 있다.

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

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

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

void dfs(int n, const vector<vector<int>>& adj, vector<bool>& visited) {
	visited[n] = true;
	for(int i = 0; i < adj[n].size(); i++) {
		int next = adj[n][i];
		if(visited[next] == 0) dfs(next, adj, visited);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t; 
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		vector<vector<int>> adj(n+1);
		vector<bool> visited(n+1);
		for(int i = 1; i <= n; i++) {
			int a; 
			cin >> a;
			adj[i].push_back(a); // 방향 그래프 이므로 한 쪽만
		}
		int con = 0;
		for(int i = 1; i <= n; i++) {
			if (visited[i] == false) {
				con++;
				dfs(i, adj, visited);
			}
		}
		cout << con << "\n";
	}
	return 0;
}