글 읽기 - 고수님들 도와주세요 ᅲᅲ union-set을 이용해서 풀었는데..

(追記) (追記ここまで)

고수님들 도와주세요 ᅲᅲ union-set을 이용해서 풀었는데..

10451번 - 순열 사이클

g22206 6년 전 0

Union-set 과 rank 를 더해 풀었습니다.

그리고 union 을 할때 두 변수의 랭크가 둘 다 0 이면 카운터를 증가 시켰습니다.

왜냐하면 랭크가 둘 다 0이라는 것은 최초의 집합을 만든다는 것이니까요.

그래서 테스트는 다 통과했는데

왜 틀렸다고 나올까요??

#include <cstdio>
#include <algorithm>
using namespace std;
int parent[1004], ranks[1004];
int T, N;
int cnt;
int Find(int x) {
	if (x == parent[x]) {
		return x;
	}
	else {
		int y = Find(parent[x]);
		parent[x] = y;
		return y;
	}
}
void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (ranks[x] == 0 && ranks[y] == 0)
		cnt++;
	if (ranks[x] > ranks[y])
		parent[y] = x;
	else {
		parent[x] = y;
		if (ranks[x] == ranks[y])
			ranks[y]++;
	}
}
int main() {
	scanf("%d", &T);
	int num;
	while (T--) {
		scanf("%d", &N);
		cnt = 0;
		for (int i = 0; i <= N; i++) {
			parent[i] = i;
			ranks[i] = 0;
		}
		for (int i = 1; i <= N; i++) {
			scanf("%d", &num);
			Union(i, num);
		}
		printf("%d\n", cnt);
	}
	return 0;
}