백준 10451번: 순열 사이클

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

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개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

 

 

코드

 

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

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

int ans = 0;

void dfs(int node) {
	if(visited[node] == 1) ans++;

	visited[node] = 1;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next);
	}
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N;

		for(int j = 1; j <= N; j++) { // 인접행렬 (j, M) (M, j)
			cin>>M;
			adj[j].push_back(M);
			adj[M].push_back(j);
		} 

		for(int j = 1; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j);
			}


		cout<<ans<<'\n';

		// 인접 행렬, 방문 노드, ans 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
			ans = 0;
		}
	}
}