Given a graph, program that presents, in alphabetical order, the probable friends-CodePudding

I'm a beginner in python, I'm having trouble solving an exercise on graph, the exercise is as follows:

Given a graph representing the social network's relationships, create a program that lists 'Mussum's' likely friends in alphabetical order. To find 'Mussum's' likely friends, consider the following rule: two disconnected people who have at least 3 mutual friends have a high probability of being friends with each other and therefore are likely friends.

Input:

The first line of the input indicates how many n vertices there are in the graph (1 ≤ n ≤ 100). The next n lines each represent the information of a vertex in the format: id, A, v1, v2,⋯,vA, where id is a string that identifies the vertex, A is the number of edges connected to this vertex, and each vi ≠ id is a string that identifies a vertex adjacent to id. The first id is always Mussum's.

Exit:

Show, in alphabetical order, Mussum's probable friends, and if none, print the message "No friends"

For example:

Input:

Mussum 3 Didi Dede Zacarias

Zacarias 5 Didi Dede Macale Mussum Sargento

Dede 5 Didi Macale Mussum Zacarias Sargento

Didi 5 Mussum Dede Macale Zacarias Sargento

Sargento 4 Didi Dede Zacarias Macale

Macale 4 Sargento Didi Dede Zacarias

Output:

Macale

Sargento

Input:

Mussum 3 Sorvetao Conrado Dede

Dede 2 Sorvetao Mussum

Sorvetao 3 Mussum Conrado Dede

Conrado 2 Mussum Sorvetao

Output:

"No friends"

My code for this problem so far has been this as I haven't been able to solve the problem. Code:

graph = {}
for _ in range(int(input())):
  v, A, *neighbor = input().split()
  graph[v] = neighbor

friend_of_friends = {}
for friend in graph['Mussum']:
  for friends_neighbor in graph[friend]:
    if friends_neighbor in friend_of_friends:
      friend_of_friends[friends_neighbor]  = 1
    else:
      friend_of_friends[friends_neighbor] = 1

CodePudding user response：

You were off to a great start. The friends_of_friends dictionary contains all the information that you need to get the results. The friends_of_friends dictionary contains for each person the number of his/her mutual friends with Mussum. You then just need to check if the number meets the requirements and then just add some logic to ensure that you return the likely friends in alphabetical order and that you for example do not report Mussum as his own likely friend. A possible solution might look something like this:

graph = {}
for _ in range(int(input())):
  v, A, *neighbor = input().split()
  graph[v] = neighbor

friend_of_friends = {}
for friend in graph['Mussum']:
  for friends_neighbor in graph[friend]:
    if friends_neighbor in friend_of_friends:
      friend_of_friends[friends_neighbor]  = 1
    else:
      friend_of_friends[friends_neighbor] = 1

likely_friends = []
for possible_likely_friend, mutual_friends_count in friend_of_friends.items():
  # Skip checking if Mussum is a likely friend of himself
  if possible_likely_friend == 'Mussum':
    continue

  # Do not report people that are already friends with Mussum as likely friends
  if possible_likely_friend in graph['Mussum']:
    continue

  # If the person has at least 3 mutual friends with Mussum, add the person to the list
  if mutual_friends_count >= 3:
    likely_friends.append(possible_likely_friend)

# If there are some likely friends, first sort them alphabetically and then output
# them each on one line. If no likely friends, output "No friends".
if likely_friends:
  likely_friends.sort()
  for likely_friend in likely_friends:
    print(likely_friend)
else:
  print("No friends")