글 읽기 - Disjoint set으로 size배열을 이용했을 때의 오답 질문

cesta123 4년 전 0

기존에는 for(int i=2; i<=N; i++) if(Find(1) == Find(i)) ++ans;으로 정답을 구하긴 했었습니다. Union을 하면서 각 컴퓨터 번호에 대해 Size를 계산하고 출력하는 형식으로 해보려 바꾸어 보았는데 오답이 나와서 질문드립니다. 1번 컴퓨터에 대한 set size를 구하고, 1번 컴퓨터를 제외한 나머지 수를 출력하면 된다고 생각했는데 이 방법이 틀린건가요? 질문에 있는 반례를 넣어보아도 틀린 반례를 찾기 어려워서 질문드립니다.

#include <iostream>
using namespace std;
int parent[101];
int Size[101];
int Find(int x){
	if (x == parent[x]) return x;
	else return parent[x] = Find(parent[x]);
}
int Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if (x != y){
		parent[y] = x;
		Size[x] += Size[y];
	}
	return Size[x];
}
int main(){
	int N, M;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++){
		parent[i] = i;
		Size[i] = 1;
	}
	scanf("%d", &M);
	for (int i = 0; i<M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		Union(x, y);
	}
	printf("%d\n", Size[1] - 1);
}

kcm1700 4년 전 1

Size[1]이 아니라 Size[Find(1)]을 의도하신 거 같네요.

cesta123 4년 전 0

감사합니다. 테스트케이스 중에 (X 1) 이런식으로 1이 오른쪽으로만 들어오는 테스트케이스도 있기 때문이라고 해석해도 될까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Disjoint set으로 size배열을 이용했을 때의 오답 질문

cesta123 4년 전 0

kcm1700 4년 전 1

cesta123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말