글 읽기 - 틀린이유를 모르겠습니다.

asd311sw 4년 전 0

union find를 이용해 풀었고요, 게시판 반례 넣어봐도 다 잘나오는데 어디서 틀린건지 모르겠습니다.

#include <stdio.h>
#include <stdlib.h>

int getParent(int parent[], int n) {
	if (parent[n] == n) {
		return n;
	}
	else {
		return getParent(parent, parent[n]);
	}
}

void unionParent(int parent[], int n1, int n2) {
	int p1 = getParent(parent, n1);
	int p2 = getParent(parent, n2);

	if (p1 < p2) {
		parent[n2] = p1;
	}
	else {
		parent[n1] = p2;
	}
}

int isParent(int parent[], int n1, int n2) {
	int p1 = getParent(parent, n1);
	int p2 = getParent(parent, n2);

	if (p1 == p2) {
		return p1;
	}
	else {
		return 0;
	}
}



int main(void) {
	int n, m;
	scanf("%d %d", &n, &m); getchar();

	int* parent = (int*)malloc(sizeof(int) * (n + 1));
	int* arr = (int*)malloc(sizeof(int) * (n + 1));

	for (int i = 1; i < n + 1; i++) {
		parent[i] = i;
	}

	for (int i = 1; i < n + 1; i++) {///부모노드 정보
		arr[i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int v1, v2;
		scanf("%d %d", &v1, &v2); getchar();

		unionParent(parent, v1, v2);
	}

	int count = 0;

	for (int i = 1; i < n + 1; i++) {
		if (arr[getParent(parent, i)] == 0) {
			arr[getParent(parent, i)]++;
		}
	}

	for (int i = 1; i < n + 1; i++) {
		if (arr[i] > 0) {
			count++;
		}
	}

	printf("%d", count);
}

kyo20111 4년 전 1

https://www.acmicpc.net/board/view/17808

게시판의 예제를 모두 확인한 뒤에 글을 올려주세요

asd311sw 4년 전 0

감사합니다! 확인해보지않은 반례가 있었군요. 덕분에 무사히 해결했습니다.

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

문제

문제

출처

ICPC

틀린이유를 모르겠습니다.

asd311sw 4년 전 0

kyo20111 4년 전 1

asd311sw 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말