Overview

This problem asks you to count the number of mutual friend request pairs from \(M\) friend requests, where “A requests B” AND “B requests A”.

Analysis

Key Insight

The key point of this problem is how to determine if two people have “mutually requested” each other.

For example, suppose we have the following friend requests: - Student 1 → Student 2 (1 requests 2) - Student 3 → Student 1 (3 requests 1) - Student 2 → Student 1 (2 requests 1)

In this case, Student 1 and Student 2 have mutually requested each other, forming 1 pair.

Problems with the Naive Approach

The naive approach would be to check for every request pair whether the reverse request exists.

for each request(A, B):
    for search through all requests again to check if (B, A) exists

This method requires searching up to \(M\) requests for each request, resulting in \(O(M^2)\) time complexity. When \(M\) is at most \(2 \times 10^5\), this becomes approximately \(4 \times 10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Solution: Using a Set

Using Python’s set, we can check for element existence in average \(O(1)\) time.

While reading each request one by one: 1. Check if the reverse request \((B, A)\) already exists in the set 2. If it exists, a mutual request pair is formed → increment the count 3. Add the current request \((A, B)\) to the set

Algorithm

1. Prepare an empty set requests to manage friend requests
2. Initialize counter count to 0
3. For each friend request \((A, B)\):
   • If \((B, A)\) is contained in requests, increment count by 1
   • Add \((A, B)\) to requests
4. Output the final count

Step-by-Step Example

Input example:

3 4
1 2
2 3
2 1
3 2

Step	Request	Set State	(B,A) exists?	count
1	(1,2)	{(1,2)}	(2,1) no	0
2	(2,3)	{(1,2),(2,3)}	(3,2) no	0
3	(2,1)	{(1,2),(2,3),(2,1)}	(1,2) yes!	1
4	(3,2)	{(1,2),(2,3),(2,1),(3,2)}	(2,3) yes!	2

Answer: 2 pairs

Complexity

• Time Complexity: \(O(M)\)
  • For each request, both adding to the set and checking existence take average \(O(1)\) time
• Space Complexity: \(O(M)\)
  • We store up to \(M\) requests in the set

Implementation Notes

• Python’s set can store tuples as elements, so we can manage requests in the format (A, B)
• To handle large amounts of input, we use sys.stdin.readline for faster input reading
• By processing requests sequentially as they are read, we don’t need to hold all data at once, allowing for efficient processing

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    
    # Manage friend requests using a set
    requests = set()
    count = 0
    
    for _ in range(M):
        A, B = map(int, input().split())
        # Check if the reverse request already exists
        if (B, A) in requests:
            count += 1
        requests.add((A, B))
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.