概要

\(M\) 件の友達申請の中から、「AがBに申請」かつ「BがAに申請」という相互申請のペア数を数える問題です。

考察

重要な気づき

この問題のポイントは、「相互に申請している」ことの判定方法です。

例えば、以下のような友達申請があったとします： - 生徒1 → 生徒2（1が2に申請） - 生徒3 → 生徒1（3が1に申請） - 生徒2 → 生徒1（2が1に申請）

このとき、生徒1と生徒2は相互に申請し合っているので、1ペアとなります。

素朴なアプローチの問題点

素朴に考えると、すべての申請ペアに対して逆方向の申請があるか確認したくなります。

for 各申請(A, B):
    for 全ての申請を再度探索して(B, A)があるか確認

この方法では、各申請について最大 \(M\) 件を探索するため、\(O(M^2)\) の時間がかかります。\(M\) が最大 \(2 \times 10^5\) のとき、約 \(4 \times 10^{10}\) 回の操作となり、TLE（時間制限超過）になってしまいます。

解決策：集合（Set）を使う

Pythonの set を使えば、要素の存在確認が平均 \(O(1)\) で行えます。

申請を1件ずつ読み込みながら： 1. 逆方向の申請 \((B, A)\) が既にセットに存在するか確認 2. 存在すれば、相互申請のペアが成立 → カウントを増やす 3. 現在の申請 \((A, B)\) をセットに追加

アルゴリズム

1. 友達申請を管理するための空の集合 requests を用意する
2. カウンター count を 0 に初期化する
3. 各友達申請 \((A, B)\) に対して：
   • \((B, A)\) が requests に含まれていれば count を 1 増やす
   • \((A, B)\) を requests に追加する
4. 最終的な count を出力する

具体例での動作

入力例：

3 4
1 2
2 3
2 1
3 2

処理	申請	セットの状態	(B,A)がある？	count
1	(1,2)	{(1,2)}	(2,1)なし	0
2	(2,3)	{(1,2),(2,3)}	(3,2)なし	0
3	(2,1)	{(1,2),(2,3),(2,1)}	(1,2)あり！	1
4	(3,2)	{(1,2),(2,3),(2,1),(3,2)}	(2,3)あり！	2

答え：2ペア

計算量

• 時間計算量: \(O(M)\)
  • 各申請に対して、セットへの追加と存在確認がそれぞれ平均 \(O(1)\) で行えるため
• 空間計算量: \(O(M)\)
  • 最大 \(M\) 件の申請をセットに保存するため

実装のポイント

• Pythonの set はタプルを要素として格納できるので、(A, B) の形式で申請を管理できます

• 入力が大量の場合に備えて、sys.stdin.readline を使用することで高速に入力を読み込んでいます

• 申請を読み込みながら逐次処理することで、一度にすべてのデータを保持する必要がなく、効率的に処理できます

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    
    # 友達申請をセットで管理
    requests = set()
    count = 0
    
    for _ in range(M):
        A, B = map(int, input().split())
        # 逆方向の申請が既にあるかチェック
        if (B, A) in requests:
            count += 1
        requests.add((A, B))
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。