AtCoder ABC 278 C - FF (4Q, 灰色, 300 点)

SNS を題材にした set の練習問題

• 問題へのリンク

問題概要

人から SNS について、次の 個のクエリに答えよ（初期状態では全員が誰もフォローしていない）。

• クエリタイプ 1：人 が人 をフォローする（フォロー済みの場合は何もしない）
• クエリタイプ 2：人 が人 のフォローを解除する（フォローしてない場合は何もしない）
• クエリタイプ 3：人 が相互にフォローし合っているかどうかを判定する

制約

• 
• 

考えたこと

人 が人 をフォローしている状態をペア値 {A, B} で表すことにしよう。そうして、フォロー関係すべてを表す集合 S を次のように定義しよう。

---

S：フォロー関係 {A, B} を格納した集合

---

C++ であれば、具体的には set<pair<int, int>> 型で実現できる。そうすると次のように実装できる。

• 人 が人 をフォローする：S.insert({A, B})
• 人 が人 のフォローを解除する：S.erase({A, B})
• 人 が相互フォローであるかを確認する：S.count({A, B}) && S.count({B, A}) が true かどうかで判定

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q, T, A, B;
    cin >> N >> Q;

    set<pair<int,int>> S;
    while (Q--) {
        cin >> T >> A >> B;
        if (T == 1) S.insert({A, B});
        else if (T == 2) S.erase({A, B});
        else {
            if (S.count({A, B}) && S.count({B, A})) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}