친구의 친구 사이는 친구이므로, 각 사람들에 대해 서로 가장 가까운 정도를 구할 수 있다.
구해진 가까운 정도(최단 경로)들이 가장 작은 사람들의 리스트를 만들어 출력한다.
#include <cstdio>
#define INF 987654321
int main(){
int i, j, k, n;
int g[101][101];
scanf("%d ", &n);
for(i=0; i<n; ++i)
for(j=0; j<n; ++j)
g[i][j] = i==j?0:INF;
int a, b, c;
while(~scanf("%d %d ", &a, &b) && a>0)
g[a-1][b-1] = g[b-1][a-1] = 1;
for(k=0; k<n; ++k){
for(i=0; i<n; ++i){
for(j=0; j<n; ++j){
if(g[i][k]+g[k][j] < g[i][j])
g[i][j] = g[i][k]+g[k][j];
}
}
}
int len=0, cand[50]={}, minR=INF;
for(i=0; i<n; ++i){
int maxi = 0;
for(j=0; j<n; ++j)
if(maxi < g[i][j]) maxi=g[i][j];
if(maxi <= minR){
if(maxi != minR) len=0;
cand[len++] = i+1;
minR = maxi;
}
}
printf("%d %d\n", minR, len);
for(i=0; i<len; ++i) printf("%d ", cand[i]);
return 0;
}
댓글 없음:
댓글 쓰기