글 읽기 - 도대체 왜틀렸는지 잘 모르겠습니다..

dksu40 4년 전 0

유니온 파인드를 쓰지 않고 최댓값을 비교하여 넣은뒤 최솟값을 뽑아내는 식으로 진행했는데,

반례 다 맞는데 어디서 틀렸는지 의문입니다.

#include <bits/stdc++.h>
using namespace std;
#define MM 102
int A[MM][MM];
int grup[MM];
vector<pair<int, int>> ans[MM];

int main()
{
	int N, K; cin >> N >> K;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
			if (!A[i][j]) A[i][j] = 100000;
	}
	for (int i = 1; i <= K; i++)
	{
		int a, b;
		cin >> a >> b;
		A[a][b] = 1;
		A[b][a] = 1;
	}
    //초기화 후 입력까지 한 부분
    
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				A[i][j] = min(A[i][j],A[i][k] + A[k][j]);
    //플로이드 와샬
    

	int grp = 1;
	int flag=0;
	for (int i = 1; i <= N; i++)
	{
		int dcnt = 0;
		for (int j = 1; j <= N; j++)
		{
			if (!grup[j]&&A[i][j]!= 100000)
			{
				grup[j] = grp; flag = 1;
			}
			if (A[i][j] == 100000) dcnt++;
		}
		if (dcnt == N)
		{
			grup[i] = grp; flag = 1;
		}
		if(flag) grp++;
		flag = 0;
	}
    grp--;
    // 1~N번까지 그룹 지어주는 코드 => grup[i번사람] = 그룹의 번호 로 저장됨.
    
    
	for (int i = 1; i <= N; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= N; j++)
		{
			if (i == j)continue;
			if (A[i][j] != 100000) cnt = max(cnt, A[i][j]);
		}
		ans[grup[i]].push_back({ cnt,i });
	}
    // 문제가 물어보는 의사전달시간의 최댓값을 
    // 1~N번 사람이 각각 대표인 경우에 멎춰서 ans배열에 넣어주는 코드
    // ans[그룹의 번호].push_back({의사전달시간의 최대, 대표자의 번호})
    
	for (int i = 1; i <= N; i++)
	{
		sort(ans[i].begin(), ans[i].end());
	}
    // 그룹별로 담은 최댓값에서 최소를 보기위해 정렬.

	cout << grp << '\n';
	for (int i = 1; i <= grp; i++)
	{
		cout << ans[i].front().second << '\n';
	}
    // 답안 출력
}

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

문제

문제

출처

ICPC

도대체 왜틀렸는지 잘 모르겠습니다..

dksu40 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말