Overview

Given \(N\) students, find the number of pairs who have mutually sent friend requests to each other.

Discussion

Friend requests are sent “one-directionally” — just because student \(A\) has sent a request to \(B\) does not necessarily mean \(B\) has also sent a request to \(A\).
To satisfy the condition of “mutually sent friend requests,” both \((A, B)\) and \((B, A)\) must be present in the input.

A naive approach would be, for every request \((A_i, B_i)\), to check whether the reverse request \((B_i, A_i)\) exists each time, but this results in \(O(M^2)\) in the worst case, which will not fit within the time limit.

Instead, to efficiently manage who each student has sent requests to, we use an adjacency list representation with sets. This allows us to check whether a student \(A\) has sent a request to student \(B\) in \(O(1)\).

Furthermore, for each pair \((A, B)\), if \(A\) has sent a request to \(B\) and \(B\) has also sent a request to \(A\), we determine them to be “mutual.” However, this method counts the same pair twice (counted for both \((A, B)\) and \((B, A)\)), so we divide by 2 at the end.

For example, given the following input:

3 4
1 2
2 1
2 3
3 2

• Student 1 ↔ Student 2 are mutual
• Student 2 ↔ Student 3 are mutual
  Therefore, the answer is 2.

Algorithm

1. Store who each student has sent friend requests to using defaultdict(set).
2. For every request \((A, B)\), check whether \(B\) has sent a request to \(A\).
3. If they are mutual, increment the count.
4. Finally, divide the count by 2 and output (to remove duplicates).

Complexity

• Time complexity: \(O(M)\)
• Space complexity: \(O(M)\)

Implementation Notes

• By storing each student’s friend request targets in a set, membership checks can be performed efficiently.

• Since the same pair is counted twice, do not forget to divide the result by 2.

• sys.stdin.read is used to read input quickly.

  Source Code

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    friends = defaultdict(set)
    
    index = 2
    for _ in range(M):
        A = int(data[index])
        B = int(data[index+1])
        friends[A].add(B)
        index += 2
    
    count = 0
    for a in friends:
        for b in friends[a]:
            if b in friends and a in friends[b]:
                count += 1
    
    # Each pair is counted twice (a,b) and (b,a), so divide by 2
    print(count // 2)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.