グラフに落とし込む

この問題を社員を頂点とし、直接のじゃんけん結果を辺とするグラフを考えます。

このグラフ上でクエリ1は頂点$X$と頂点$Y$の間に辺を張ることに対応します。 また、クエリ2は頂点$X$の部分グラフの頂点数を求めることに対応します。（正確には部分グラフから頂点$X$の分の1を引く必要があります。） クエリ3はグラフの連結成分数を数えることに対応します。

隣接リストでグラフを表現することで、クエリ1は$O(1)$、クエリ2はDFS等で$O(N)$、クエリ3はDFS等で$O(N)$でそれぞれ実装することが出来ます。 しかし、クエリ全体での計算量が$O(NQ)$になってしまい実行時間制限に間に合いません。

クエリ2の高速化

ここで、「クエリ1が与えられる直前の時点で、社員$X$と社員$Y$はどちらも上司を一人も持たない」という条件に着目します。 この条件から一度じゃんけんに敗北した社員は、それ以降じゃんけんをすることは無く、部下の数が増えることも減ることもありません。

従って、必要な情報は「じゃんけんの勝者の部下が何人増えたか」という情報のみです。つまり、その時点での部下の人数を管理することで$O(1)$にクエリを処理することが出来ます。

クエリ3の高速化

グラフの連結成分数はじゃんけんが一度行われるごとに、1減ります。 つまり、そのクエリ3が呼び出されるまでに行われたじゃんけんの回数を管理することで答えを$O(1)$で求めることが出来ます。

計算量

• 配列の確保：$O(N)$
• クエリ1への回答：$O(1)$
• クエリ2への回答：$O(1)$
• クエリ3への回答：$O(1)$
• 全体：$O(N+Q)$

ACコード

xxxxxxxxxx

#include <bits/stdc++.h>

using namespace std;

​

int main() {

    int N,Q;

    cin >> N >> Q;

    vector<int> rank(N, 1);

    int groupNum = N;

​

    for (int i = 0; i < Q; ++i) {

        int T;

        cin >> T;

        if (T == 1) {

            int X,Y;

            cin >> X >> Y;

            --X; --Y;

            rank[X] += rank[Y];

            --groupNum;

        } else if (T == 2) {

            int X;

            cin >> X;

            --X;

            cout << rank[X] - 1 << "\n";

        } else if (T == 3) {

            cout << groupNum << "\n";

        }

    }

}