글 읽기 - 어느 부분이 틀렸는지 모르겠습니다.

supremejin03 8년 전 0

플로이드로 최단거리 구하고, Union Find를 통하여 그룹핑 한 후 같은 그룹 내에서 최대값이 가장 작은 번호를 리더로 정하여 출력하였는데

어느 테스트 케이스에서 틀렸는지 모르겠습니다.

#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, g[102], arr[102][102] = {};
vector<int> p[102] = {};

int findG(int x) {
	if (x == g[x]) return x;
	return g[x] = findG(g[x]);
}
void unionG(int a, int b) {
	int x = findG(a);
	int y = findG(b);

	g[y] = x;
}

int main() {
	cin >> n >> m;

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

		arr[a][b] = arr[b][a] = 1;
        //그룹핑
	   	unionG(a, b);
	}

    //플로이드를 통하여 각 점에서 이동할 수 있는 최단거리 구함
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][k] != 0 && arr[k][j] != 0) {
					if (i == j) continue;
					if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
    
    //각 점에서 갈 수 있는 점의 최단거리중 max 값 저장
	for (int i = 1; i <= n; i++) {
		int maxi = 0;
		for (int j = 1; j <= n; j++) {
			if (maxi < arr[i][j]) maxi = arr[i][j];
		}
		arr[i][n + 1] = maxi;
	}

	//위원회 별 묶음
	for (int i = 1; i <= n; i++) {
		int a = g[i];
		p[a].push_back(i);
	}

	int cnt = 0;
	int ans[102];
    //각 그룹내 리더 정해줌
	for (int k = 1; k <= n; k++) {
		int s = p[k].size();
		if (s > 0) {
			int maxi = 0x7fffffff;
			int leader = p[k][0];
			for (int i = 0; i < s; i++) {
				int a = p[k][i];
				if (maxi > arr[a][n + 1]) {
					maxi = arr[a][n + 1];
					leader = a;
				}
			}
			ans[cnt++] = leader;
		}
	}
	cout << cnt << "\n";

	sort(ans, ans + cnt);

	for (int i = 0; i < cnt; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

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

문제

문제

출처

ICPC

어느 부분이 틀렸는지 모르겠습니다.

supremejin03 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말