백준 2610: 회의준비 - 플로이드–와샬 C++

https://www.acmicpc.net/problem/2610

2610번: 회의준비

#include <bits/stdc++.h>
using namespace std;


int n,k;
int dist[101][101];
bool grouped[101];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		dist[a][b] = 1;
		dist[b][a] = 1;
	}

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

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	
	int cnt = 0;

	vector<int> king;

	for (int i = 1; i <= n; i++) {
		vector<int> g;
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] < 200 && grouped[j] == false) {
				grouped[j] = true;
				g.push_back(j);
			}
		}
		
		if (g.size() > 0) {
			cnt++;

			int minn = INT_MAX;
			int midx = -1;

			for (int j = 0; j < g.size(); j++) {

				int maxx = 0;
				for (int k = 0; k < g.size(); k++) {
					maxx = max(maxx, dist[g[j]][g[k]]);
				}
				if (maxx < minn) {
					minn = maxx;
					midx = g[j];
				}
			}
			king.push_back(midx);
		}
	}

	sort(king.begin(), king.end());

	cout << cnt << '\n';
	for (int i = 0; i < king.size(); i++) {
		cout << king[i] << '\n';
	}

	return 0;
}

백준 2610번