質問する

W杯サッカーを応援するパーティーで会長を選ぶつもりだ.このパーティーが成立して間もなく、会員の間には知らない人もいますが、何人かを通じてお互いに知ることができます.各会員は他の会員に近い程度によって点数を得る.
たとえば、ある会員が他のすべての会員と友人である場合、その会員の点数は1点です.ある会員の点数が2点であれば、他のすべての会員が友人や友人の友人であることを示します.また、ある会員の点数が3点であれば、他のすべての会員が友人、友人の友人、友人の友人であることを示す.
4点、5点などは同じ方法で決めます.各会員に点数をつけるときに注意しなければならないのは、2人の会員が友达で、同時に友达の友达であれば、この2人は友达です.
会長は会員の中で点数が一番小さい人になる.会長の点数と会長になれるすべての人を探すプログラムを書いてください.

入力

入力した最初の行には会員数があります.ただし、会員数は50名を超えない.2行目の後、1行には2つの会員番号があり、2人の会員が互いに友达であることを示しています.会員番号は1から会員数があります.最後の行には2つの-1があります.

しゅつりょく

1行目は会長候補者の点数と候補者数を出力し、2行目は会長候補者を昇順に出力する.

に答える

これは難しそうに見える問題であるが,実際には開始ノードから各ノードまでの距離を求める問題である.もし1~7番の人がいたら?最も遠いノードの長さを求めればいいです.
各ノードにdistを作成し、各ノードの長さを格納するリストを作成します.1−>3−>6−>7のノードであれば,3番は1から+1,6番は3から+1,7番は6から+1,7番は3の値を得ることができる.

import sys
sys.stdin= open('input.txt')
from collections import deque
N = int(input())
graph = [[]for _ in range(N+1)]
score = list(range(N))
while True:
    a,b = map(int,input().split())
    if a==-1 :
        break
    else:
        graph[a].append(b)
        graph[b].append(a)

def bfs(start):
    Q = deque()
    visited = [False for _ in range(N+1)]
    visited[0] = True
    visited[start] = True
    Q.append(start)
    dist = [0] * (N+1) # 시작 노드부터 거리
    while Q :
        # 한명씩 확인하면서 node의 길이를 구한다
        tmp = Q.popleft()
        for i in graph[tmp]:
            if not visited[i] : # 아직 친구등록이 안되어있으면
                Q.append(i) # Q 추가 해주고
                visited[i] = True  # 친구 등록해준다
                dist[i] = dist[tmp] + 1 # 1->3 -> 2  ?? 2가된다 .
    return dist

small = 50
result =[]
for i in range(1,N+1):
    tmp = max(bfs(i))
    if score[tmp]<small:
        small = score[tmp]
        result = [i]
    elif score[tmp] == small:
        result.append(i)

print(small,len(result))
print(*result)