글 읽기 - 반례가 뭘까요?!!?!!

melon940925 4년 전 0

테스트케이스를 직접 만들어서 해보는건 다 통과하는데

왜 틀린지 모르겠어요

주석으로 설명 달아놨습니다..

어느 부분이 문제인지 알려주시면 감사하겠고

반례를 알려주신다면 더 감사하겠습니다.

#include <iostream>
using namespace std;

int parent[1002];
int arr_1[1002];
int arr_2[1002];
int flag[1002];

int find(int x) {//트리의 루트 찾기
	if (parent[x] == x)
		return x;
	else return find(parent[x]);
}

void Union(int a, int b) {//루트가 다르면 병합
	a = find(a); b = find(b);
	if (a != b) {
		if (a > b)parent[a] = b;
		else parent[b] = a;
	}
}

void QuickSort(int* arr, int left, int right) {//퀵정렬
	int pivot = arr[left];
	int l = left;
	int r = right;
	int temp;
	while (l <= r) {
		while (arr[l] < pivot)l++;
		while (arr[r] > pivot)r--;
		if (l <= r) {
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			l++; r--;
		}
	}
	if (r > left) {
		QuickSort(arr, left, r);
	}
	if (l < right) {
		QuickSort(arr, l, right);
	}

}

int main() {
	int a = 0, b = 0;
	int n;
	int except;
	int idx_1 = 0, idx_2 = 0;
	cin >> n;
	for (int i = 1; i <= 1001; i++)
		parent[i] = i;


	while (a != -1 && b != -1) {//a번 학생과 b번학생의 번호를 입력받아서 아는사이면 Union
		cin >> a >> b;
		if (a == -1 && b == -1)break;//-1을 입력받으면 break;
		if (a > n || b > n) {//a와 b는 n보다 클 수 없다.
			cout << -1 << endl;
			return 0;
		}
		Union(a, b);
		flag[a] = 1;
		flag[b] = 1;
	}

	for (int i = 1; i <= n; i++) {//한번도 입력받지 않은 학생이 있다면 어느 그룹에도 속하지 않으므로 불가능
		if (!flag[i]) {
			cout << -1 << endl;
			return 0;
		}
	}

	int x = find(1);//1번 학생이 속한 그룹의 루트는 x
	for (int i = 2; i <= n; i++) {//1번 학생이 속하지 않은 그룹의 루트는 except
		if (find(i) != x) {
			except = find(i);
			break;
		}
	}

	for (int i = 1; i <= n; i++) {//1번부터 n번 학생까지
		if (find(i) == x) {//1번학생과 같은 그룹이면 arr_1에 추가한다.
			arr_1[idx_1++] = i;
		}
		else if (find(i) == except) {//1번학생과 다른 그룹이면 arr_2에 추가한다.
			arr_2[idx_2++] = i;
		}
		else {//루트가 x도아니고 except가 아닌 제 3의 그룹이 있다면 두 그룹으로 나뉘지 않으므로 불가능
			cout << -1 << endl;
			return 0;
		}
	}

	arr_1[idx_1] = -1; arr_2[idx_2] = -1;//마지막 원소는 -1

	QuickSort(arr_1, 0, idx_1 - 1);//-1을 제외한 배열을 정렬한다.
	QuickSort(arr_2, 0, idx_2 - 1);

	cout << 1 << endl;

	//if (idx_2 == 0) {
	//	for (int i = 0; i < (int)(idx_1 / 2); i++) {
	//		cout << arr_1[i] << ' ';
	//	}
	//	cout << -1 << endl;
	//	for (int i = (int)(idx_1 / 2); i <= idx_1; i++) {
	//		cout << arr_1[i] << ' ';
	//	}
	//	cout << endl;
	//	return 0;
	//}

    
    //출력
	for (int i = 0; i <= idx_1; i++) {
		cout << arr_1[i] << ' ';
	}
	cout << endl;
	for (int i = 0; i <= idx_2; i++) {
		cout << arr_2[i] << ' ';
	}
	cout << endl;

	return 0;
}

melon940925 4년 전 0

알고보니 건너건너 아는 사이끼리는 같은그룹으로 넣을 수가 없는거였네요 ㅎㅎㅎ!!!

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

문제

문제

출처

ICPC

반례가 뭘까요?!!?!!

melon940925 4년 전 0

melon940925 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말