概要

友達申請を有向辺 \((A \rightarrow B)\) とみなし、\((A \rightarrow B)\) と \((B \rightarrow A)\) が両方存在する生徒ペアの数を数えます。

考察

相互に申請しているとは、同じ2人の間に「両方向の申請」がある状態です。つまり、申請一覧に \((A,B)\) があり、かつ \((B,A)\) もあるかを判定できればよいです。

素朴に全ての組 \((A,B)\) について逆向きがあるかを探すと、例えば各申請ごとにリストを線形探索してしまい、最悪で \(O(M^2)\) になってしまいます（\(M \le 2\times 10^5\) なので間に合いません）。

そこで、申請を「集合（set）」に入れておけば、逆向きの存在確認 \((B,A) \in \text{set}\) を平均 \(O(1)\) でできます。

また、相互関係のペアは \((A,B)\) と \((B,A)\) の2つの申請があるため、単純に両方から数えると2回カウントしてしまいます。
例えば \(1 \leftrightarrow 2\) があるとき、 - \((1,2)\) を見ても相互 - \((2,1)\) を見ても相互
となり、2回数えてしまいます。

これを防ぐために、「\(a < b\) のときだけ数える」と決めれば、各ペアをちょうど1回だけ数えられます。

アルゴリズム

1. 入力された全ての申請 \((a,b)\) を集合 edges に格納する。
2. edges の各要素 \((a,b)\) について次を行う：
   • \(a < b\) かつ \((b,a)\) も edges に存在するなら、答えを \(+1\) する。
3. 最後に答えを出力する。

計算量

• 時間計算量: \(O(M)\)（集合への追加 \(M\) 回 + 各辺のチェック \(M\) 回、いずれも平均 \(O(1)\)）
• 空間計算量: \(O(M)\)（申請を集合に保存するため）

実装のポイント

• 逆向きの存在確認を高速化するために set を使います（(b, a) in edges）。

• 二重カウント防止のため、a < b の条件を入れて「小さい番号側から見たときだけ」数えます。

• sys.stdin.readline を使うと大量入力でも高速に処理できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    edges = set()
    for _ in range(M):
        a, b = map(int, input().split())
        edges.add((a, b))

    ans = 0
    for a, b in edges:
        if a < b and (b, a) in edges:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。