Problem Description
You need to develop a program that understands user relationships in a social network.
The program must provide answers to the following two requests based on the friendships of the given users.
- Print the friend list of the given user A.
- Check whether the given users A and B are friends.
Input Format
The first line contains the number of users N and the number of friendships M. (1 ≤ N ≤ 100,000, 0 ≤ M ≤ 1,000,000)
The next M lines each contain two integers A and B, meaning A is a friend of B.
Output Format
Print the friend list of user A in ascending order on the first line.
On the second line, print ‘YES’ or ‘NO’ regarding whether A and B are friends.
Example
Input Example:
5 4
1 2
1 3
2 4
3 5
1
2
Output Example:
2 3
NO
Approach
To solve this problem, you need to efficiently store and query friendship relationships.
You can utilize graph theory by using an adjacency list or set data structure.
First, initialize an empty list to store information about users and friendship relationships.
Then, receive each friendship relationship as input and store the information.
Sort the friend list for output and also provide a response to the friendship verification request.
Source Code
def manage_friendship(n, m, friendships, a, b):
friends = {i: set() for i in range(1, n + 1)}
for x, y in friendships:
friends[x].add(y)
friends[y].add(x)
friend_list = sorted(friends[a])
is_friend = "YES" if b in friends[a] else "NO"
return friend_list, is_friend
# Input processing
n, m = map(int, input().split())
friendships = [tuple(map(int, input().split())) for _ in range(m)]
a = int(input())
b = int(input())
# Manage friendships
friend_list, is_friend = manage_friendship(n, m, friendships, a, b)
# Output results
print(" ".join(map(str, friend_list)))
print(is_friend)
Conclusion
This algorithm problem requires a basic understanding of data structures and algorithms to efficiently manage and
query friendship relationships.
In real software development, handling such data relationships often appears in platforms such as custom applications or social networks,
so learning how to solve these problems is very useful.
Appendix
Many graph problems, such as friendship relationships, can evolve into more advanced problems through searching algorithms like DFS (Depth First Search) or BFS (Breadth First Search).
Based on this problem, I hope you challenge those advanced problems as well.