2834 - 박스 정렬

step 1

$i$번째 박스를 $i$번 정점으로 생각하고 각 박스에 있는 숫자에 해당하는 정점으로 간선을 그립니다. 이렇게 하면 사이클이 생깁니다.

step 2

크기가 1인 사이클은 이미 정리가 된 것이니 전부 없애줍니다. 만약 크기가 2 이상인 사이클의 개수가 0개면 이미 정리가 된 것이니 0을 출력합니다.

 

사이클이 1개면 1번만에 정리할 수 있습니다.각 정점을 이동하면서 정점이 가리키는 숫자를 출력하면 됩니다.

step 3

사이클이 2개 이상이면 2번 만에 해결할 수 있습니다. 각 사이클에서 아무 점을 1개씩 고른 다음 섞어줍니다. 그럼 사이클이 하나로 합쳐집니다.

 

이제 사이클이 1개인 경우처럼 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
#include<queue>
using namespace std;
int b[2000],c[2000],s[2000],ss=0;
int main() {
	int n, i, countt=0;
	scanf("%d", &n);
	for (i = 1;i <= n;i++) {
		scanf("%d", &b[i]);
	}
	for (i = 1;i <= n;i++) {
		if (c[i] == 1) continue;
		int ii = i,cnt=0;
		while (c[ii] == 0) {
			cnt++;
			c[ii] = 1;
			ii = b[ii];
		}
		if (cnt >= 2) countt++;
	}
	if (countt == 0) { printf("0"); return 0; }
	if (countt == 1) {
		printf("1\n");
		for (i = 1;i <= n;i++) {
			if (i == b[i]) continue;
			int ii = i,cnt=0;
			while (1) {
				cnt++;
				ii = b[ii];
				if (ii == i) break;
			}
			printf("%d: ", cnt);
			ii = i;
			while (1) {
				printf("%d ", ii);
				ii = b[ii];
				if (ii == i) break;
			}
			return 0;
		}
	}
	for (i = 1;i <= n;i++) c[i] = 0;
	printf("2\n");
	for (i = 1;i <= n;i++) {
		if (c[i] == 1) continue;
		c[i] = 1;
		int ii = i;
		if (i == b[i]) continue;
		ss++;
		s[ss] = i;
		while (1) {
			c[ii] = 1;
			ii = b[ii];
			if (ii == i) break;
		}
	}
	printf("%d: ", ss);
	int start = b[s[ss]];
	for (i = 1;i <= ss;i++) {
		printf("%d ", s[i]);
		int tmp = b[s[i]];
		b[s[i]] = start;
		start = tmp;
	}
	printf("\n");

	for (i = 1;i <= n;i++) {
		if (i == b[i]) continue;
		int ii = i, cnt = 0;
		while (1) {
			cnt++;
			ii = b[ii];
			if (ii == i) break;
		}
		printf("%d: ", cnt);
		ii = i;
		while (1) {
			printf("%d ", ii);
			ii = b[ii];
			if (ii == i) break;
		}
		return 0;
	}
	return 0;
}