Six Degrees of Kevin Bacon
InterviewTime limit2sMemory limit128 MB
Given an unweighted friendship graph, find the vertex whose sum of shortest distances to all others is minimal, breaking ties by smallest index.
- Level
Easy3 of 10
- Topics
- BFS, Graph, Shortest path
- Solved
- No attempts yet
Problem
In the Kevin Bacon game, the distance between two people is the minimum number of acquaintance steps needed to connect them. A person's Kevin Bacon number is the sum of these minimum distances from that person to every other person.
You are given N people and M friendship relationships. Every person can reach every other person through friendships. Write a program that finds the number of the person with the smallest Kevin Bacon number. If multiple people have the same minimum value, choose the smallest number.
Input
The first line contains the number of people N (2 <= N <= 100) and the number of friendship relationships M (1 <= M <= 5,000). Each of the next M lines contains a friendship relationship A B. A and B are friends, and the relationship is bidirectional.
A and B are never the same person, but the same friendship may appear more than once. No person has zero friends, and all people are connected through friendships. People are numbered from 1 to N.
Output
Print the number of the person with the smallest Kevin Bacon number on the first line. If several people have the same minimum value, print the smallest number among them.