1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, q, w, d[102][102], a, s = 987654321, c, i, t, y;
int main() {
	cin >> N >> M;
	for (i = 0; i < M; i++) {
		cin >> q >> w;
		d[q][w] = 1;
		d[w][q] = 1;
	}
	for (i = 1; i <= N; i++)
		for (t = 1; t <= N; t++)
			if (i != t && !d[i][t])	d[i][t] = 987654321;
	for (i = 1; i <= N; i++)
		for (t = 1; t <= N; t++)
			for (y = 1; y <= N; y++)
				d[t][y] = min(d[t][y], d[t][i] + d[i][y]);
	for (i = 1; i <= N; i++) {
		c = 0;
		for (t = 1; t <= N; t++)	if (i != t)	c += d[i][t];
		if (c < s) {
			s = c;
			a = i;
		}
	}
	cout << a << endl;
}