[백준/BOJ] 백준 2610번 : 회의준비

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

2610번: 회의준비

 

유니온 파인드를 이용해서 같은 위원회를 그룹으로 묶었고, 플로이드 와샬을 통해 각 정점 간 최단거리를 저장하여, 각 그룹에서 그룹 내 다른 정점과 최댓값이 최소가 되는 정점을 구하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n;
int m;
int adj[105][105];
int parent[105];
int rank_size[105];
vector<int> group_num[105]; //해당 그룹에 속하는 정점을 저장한다
int result1;
vector<int> result2;

void pre() {
	for (int i = 0; i < 105; i++) {
		parent[i] = i;
		rank_size[i] = 1;

		for (int j = 0; j < 105; j++) {
			adj[i][j] = 987654321;

			if (i == j) {
				adj[i][j] = 0;
			}
		}
	}


}

int find(int u) {
	if (parent[u] == u) {
		return u;
	}

	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u);
	v = find(v);

	if (u == v) {
		return;
	}

	if (rank_size[u] < rank_size[v]) {
		parent[u] = v;
	}

	else {
		parent[v] = u;

		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}
}

void make_short_dist() {
	for (int k = 0; k < 105; k++) {
		for (int i = 0; i < 105; i++) {
			for (int j = 0; j < 105; j++) {

				if (adj[i][k] == 987654321 || adj[k][j] == 987654321) {
					continue;
				}

				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		merge(u, v);

		adj[u][v] = 1;
		adj[v][u] = 1;
	}

	//플로이드 와샬을 통해 최단거리를 구한다
	make_short_dist();

	set<int> group;
	set<int>::iterator it;

	for (int i = 1; i <= n; i++) {
		int this_group = find(i);

		group.insert(this_group);
		group_num[this_group].push_back(i);
	}

	for (int i = 1; i <= n; i++) {

		int this_group = i;

		if (group_num[this_group].size() == 0) {
			continue;
		}

		int temp_short_dist = 987654321;
		int temp_result = -1;

		for (int j = 0; j < group_num[this_group].size(); j++) {

			int here = group_num[this_group][j];
			int check_dist = 0;

			for (int k = 0; k < group_num[this_group].size(); k++) {
				int there = group_num[this_group][k];
				check_dist = max(check_dist, adj[here][there]);
			}

			if (temp_short_dist > check_dist) {
				temp_short_dist = check_dist;
				temp_result = here;
			}
		}

		result2.push_back(temp_result);
	}

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

	int result1 = group.size();

	cout << result1 << "\n";
	for (int i = 0; i < result2.size(); i++) {
		cout << result2[i] << "\n";
	}

	return 0;
}