Chairperson Candidates
InterviewTime limit1sMemory limit128 MB
Given a friendship graph, compute each member's eccentricity via shortest paths and report the minimum eccentricity value with all members achieving it.
- Level
Easy3 of 10
- Topics
- Graph, BFS, Shortest path
- Solved
- No attempts yet
Problem
A soccer cheering club wants to choose a chairperson. Some members do not know each other directly, but every pair of members is connected through one or more friendship links.
For each member, define that member's score as the largest value among the shortest friendship-link distances from that member to every other member. If a member is directly friends with all other members, the score is 1. If every other member is either a friend or a friend of a friend, the score is 2. Larger scores are defined in the same way.
When two members are directly friends, their distance is 1 even if they are also connected by a longer path.
A chairperson candidate is any member with the smallest score. Find that score and all possible candidates.
Input
The first line contains the number of members, n. The number of members is at most 50.
Each following line contains two member numbers a and b, meaning that the two members are friends. Member numbers are from 1 to n.
The input ends with a line containing -1 -1.
Output
On the first line, print the chairperson candidate score and the number of candidates.
On the second line, print all candidates in increasing order.