Python新手求解基于图论的社交网络潜在好友查找编程练习题

Hey there! Let's fix up your code to solve this social network potential friends problem. I'll walk through what's missing in your current approach and show you the complete working solution.

What's Missing in Your Current Code? #

Your code does a good job counting how often each person appears as a friend of Mussum's friends, but it doesn't account for the key rules of the problem:

• We need to exclude Mussum himself (since he can't be his own potential friend)
• We need to exclude people who are already Mussum's direct friends (potential friends must be unconnected to him)
• We haven't filtered for people with at least 3 common friends, sorted the results, or handled the "no friends" case properly.

Complete Working Code #

Here's the revised code that covers all the requirements:

# Build the graph from input
graph = {}
n = int(input())
for _ in range(n):
    parts = input().split()
    v = parts[0]
    # A is parts[1], but we don't need it since we can just take the rest as neighbors
    neighbors = parts[2:]
    graph[v] = neighbors

# Get Mussum's direct friends (as a set for fast lookups)
mussum_friends = set(graph['Mussum'])
friend_of_friend_counts = {}

# Count occurrences of friends-of-friends, skipping invalid candidates
for friend in mussum_friends:
    for neighbor in graph[friend]:
        # Skip Mussum himself and people already in his friend list
        if neighbor == 'Mussum' or neighbor in mussum_friends:
            continue
        # Update the count
        if neighbor in friend_of_friend_counts:
            friend_of_friend_counts[neighbor] += 1
        else:
            friend_of_friend_counts[neighbor] = 1

# Filter for people with at least 3 common friends, then sort alphabetically
potential_friends = [person for person, count in friend_of_friend_counts.items() if count >= 3]
potential_friends.sort()

# Handle output
if potential_friends:
    print(' '.join(potential_friends))
else:
    print('"No friends"')

How This Works #

Let's break down the key parts:

1. Graph Construction: We read the input and store each person's friends in a dictionary (your original code was correct here).
2. Direct Friends Set: Using a set for mussum_friends lets us check if someone is already a friend in O(1) time, which is efficient.
3. Counting Valid Friends-of-Friends: We loop through each of Mussum's friends, then their neighbors. We skip Mussum himself and anyone already in his friend list to avoid invalid candidates.
4. Filtering and Sorting: We keep only people with a count of 3 or more, then sort them alphabetically as required.
5. Output Handling: If there are potential friends, we print them space-separated. If not, we print the exact "No friends" message from the examples.

Testing the Examples #

• Example 1: The code will count Macale and Sargento each appearing 3+ times (they share all 3 of Mussum's friends), sort them to Macale Sargento, which matches the output.
• Example 2: No one meets the 3 common friends requirement, so it prints "No friends" as expected.

内容的提问来源于stack exchange，提问作者Josue Costa