출처 BOJ

순열사이클

문제

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 & ... & i & ... & n\\ \pi_{1} & ... & \pi_{i} & ... & \pi_{n} \end{array}\right)$ 로 나타냈다면, i에서 $\pi_{i}$로 간선을 이어 그래프로 만들 수 있다.

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

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

입력

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

출력

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

예제

범위체크

연산 따로 없음

풀이

그래프 링크를 지나가면서 1로 표시
표시한 곳을 다시온다면 → cycle!

코드

code

#include<cstdio>
#include<iostream>
#define MAX 1001
using namespace std;

int N,cnt;
int G[MAX],check[MAX];

void findCycle(int num){
	if(check[num] == 0){
		check[num] = 1;
		findCycle(G[num]);
	}
}

int main(){
	int testcase;
	scanf("%d",&testcase);
	while(testcase--){
		scanf("%d",&N);
		fill_n(check,N+1,0);
		cnt = 0;
		for(int i=1; i<=N; i++)
			scanf("%d",&G[i]);

		for(int i=1; i<=N; i++){
			if(check[i]==0){
				findCycle(i);
				cnt++;
			}
		}

		printf("%d\n",cnt);
	}
}

복잡도

$O(N)$
노드들을 한번씩만 지나가면서 해결 가능