글 읽기 - 반례를 못찾겠습니다.

gusdnr9875 5년 전 0

유니온파인드 기법을 왜 사용해야하는지 모르겠습니다. 원들이 서로 붙을때마다 결과개수를 줄여주고 이미붙어있는원은 표시를 해주는 식으로 하면 안되나요?

#include <iostream>
#include <cstring>
using namespace std;
int arr[3001][3];
int arr2[3001] = { 0 };


int main()
{
	int t = 0, n = 0, x = 0, y = 0, r = 0, n_copy = 0;
	ios_base::sync_with_stdio(false);

	cin >> t;
	while (t--)
	{

		cin >> n;
		n_copy = n;
		for (int i = 1; i <= n; i++) arr2[i] = 0;

		for (int j = 1; j <= n; j++)
		{

			for (int i = 0; i < 3; i++) cin >> arr[j][i];
			for (int i = 1; i < j; i++)
			{
				int a, b;
				a = (arr[i][0] - arr[j][0])*(arr[i][0] - arr[j][0]) + (arr[i][1] - arr[j][1])*(arr[i][1] - arr[j][1]);
				b = (arr[i][2] + arr[j][2])*(arr[i][2] + arr[j][2]);
				if (a <= b && (arr2[i] == 0 || arr2[j] == 0)) {
					n_copy--;
					arr2[i] = 1, arr2[j] = 1;
				}
			}

		}
		cout << n_copy << '\n';
	}


}

djm03178 5년 전 3

유니온 파인드를 하지 않아도 됩니다. 하지만 이런 방법으로 하려면 트리의 형태는 유지해야 합니다.

이미 두 부대가 각각 어떤 그룹에 속해있지만, 그 그룹이 서로 다를 수도 있는데 이때 둘이 만나게 되면 그룹 수가 하나 줄어야 합니다. 아래 케이스의 정답은 1인데 2가 출력됩니다.

gusdnr9875 5년 전 0

정말 감사합니다! 이해했습니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

gusdnr9875 5년 전 0

djm03178 5년 전 3

gusdnr9875 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말