백준 2660 : 회장뽑기

www.acmicpc.net/problem/2660

2660번: 회장뽑기

친구 사이의 관계가 1, 친구의 친구 사이의 관계가 2, 친구의 친구의 친구 사이의 관계가 3 ... 이런  식일 때 가장 인싸를 찾는 문제이다. 간선의 가중치가 1인 그래프로 보고 풀면된다. 각각의 노드에서 모든 노드까지의 최단 경로를 구하고 해당 노드에서 다른 노드까지의 거리의 최대값이 가장 작은 사람을 회장으로 뽑으면 된다. 간선의 가중치가 모두 동일하므로 bfs를 돌려도 되고 플로이드워셜을 써도 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector<int> peer[51];
vector<int> max_lvl[51];
bitset<51> visited;

void bfs(int n) {
	int who, lvl;
	queue<pair<int, int>> q; // who, lvl
	q.emplace(n, 0);
	visited[n] = 1;

	while (!q.empty()) {
		who = q.front().first, lvl = q.front().second;
		q.pop();

		for (int i = 0; i < peer[who].size(); i++) {
			if (visited[peer[who][i]]) continue;
			q.emplace(peer[who][i], lvl + 1);
			visited[peer[who][i]] = 1;
		}
	}
	max_lvl[lvl].push_back(n);
	visited.reset();
}

int main() {
	fastio;
	int n, a, b;
	cin >> n;
	while (1) {
		cin >> a >> b;
		if (a + b < 0) break;
		peer[a].push_back(b);
		peer[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) bfs(i);
	for (int i = 1; i <= n; i++) {
		if (max_lvl[i].size() > 0) {
			cout << i << ' ' << max_lvl[i].size() << '\n';
			for (int j = 0; j < max_lvl[i].size(); j++) {
				cout << max_lvl[i][j] << ' ';
			}
			break;
		}
	}
	return 0;
}

메모리: 2020 KB

시간: 0 ms