글 읽기 - 2610 번 어떤점이 잘못됬을까요?

showme011 8년 전 0

disjoint -set 이용해서

그룹의 개수를 세고

그 그룹마다 거리의 최대값이 가장 작은 친구를

출력하게 구상하였는데 잘 안되네요

고수님들 도와주세요

#include<iostream>
#include<cstdio>
using namespace std;
#pragma warning (disable:  4996)

#define BIG 987654321

int p[101];
int d[101][101];
int group[101];
int index;
int cnt;

int find(int x)
{
	if (p[x] == x)
		return x;
	
	return p[x] = find(p[x]);

}

void Union(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x != y)
		p[y] = x;
}

int main()
{
	int N, M;
	int a, b;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
		p[i] = i;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
		{
			if (i == j)
				d[i][j] = 0;
			else
				d[i][j] = BIG;
		}

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &a, &b);
		d[a][b] = 1;
		d[b][a] = 1;
	}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (i != j && d[i][j] < BIG)
				Union(i, j);

	for (int i = 1; i <= N; i++)
		if (p[i] == i)
			group[cnt++] = i;

	printf("%d\n", cnt);

	for (int itr = 0; itr < cnt; itr++)
	{
		int temp[101];
		int idx = 0;
		int MIN = BIG;
		int midx;

		for (int i = 1; i <= N; i++)
			if (group[itr] == p[i])
				temp[idx++] = i;

		midx = temp[0];

		for (int i = 0; i < idx; i++)
		{
			int mmax = -1;
			
			for (int j = 0; j < idx; j++)
			{
				if (mmax < d[temp[i]][temp[j]])
					mmax = d[temp[i]][temp[j]];
			}

			if (mmax < MIN)
			{
				MIN = mmax;
				midx = temp[i];
			}
		}

		printf("%d\n", midx);
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

2610 번 어떤점이 잘못됬을까요?

showme011 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말