网易游戏笔试题

#include <algorithm>
#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

vector<int> retCount(vector<vector<int>> &operations) {
    vector<int> ans;

    vector<unordered_set<int>> operSets;

    for (const auto &opers:operations) {
        // 合并整数XY
        // 如果XY在一个集合中，则不做任何操作，
        // 如果XY不在一个集合中，则将它们所在的集合合并
        if (opers[0] == 1) {
            unordered_set<int> set1;
            unordered_set<int> set2;
            int x = -1, y = -1;

            for (int i = 0; i < operSets.size(); i++) {
                if (operSets[i].find(opers[1]) != operSets[i].end()) {
                    x = i;
                }

                if (operSets[i].find(opers[2]) != operSets[i].end()) {
                    y = i;
                }
            }

            // 整数X,Y不在任何集合中
            if (x == -1 && y == -1) {
                // 将整数XY合并为一个集合插入集合数组中
                unordered_set<int> tmpSet;
                tmpSet.insert(opers[1]);
                tmpSet.insert(opers[2]);
                operSets.push_back(tmpSet);
            }

            // 整数X在某个集合中，整数Y不在任何集合中
            if (x > -1 && y == -1) {
                // 将整数Y插入到集合X所在的集合中
                operSets[x].insert(opers[2]);
            }

            if (x == -1 && y > -1) {
                operSets[y].insert(opers[1]);
            }

            // 整数X和整数Y在不同集合中
            if (x > -1 && y > -1 && x != y) {
                // 将两集合合并后插入集合数组中
                unordered_set<int> tmpSet;
                tmpSet.insert(operSets[x].begin(), operSets[x].end());
                tmpSet.insert(operSets[y].begin(), operSets[y].end());
                operSets.push_back(tmpSet);

                // 删除集合数组中的原两集合
                operSets[x].clear();
                operSets[y].clear();

                if (x > y) {
                    operSets.erase(operSets.begin() + x);
                    operSets.erase(operSets.begin() + y);
                } else {
                    operSets.erase(operSets.begin() + y);
                    operSets.erase(operSets.begin() + x);
                }
            }
        }

        // 拆分整数X
        // 如果整数X不在集合中，不做任何操作
        // 如果整数X在某个集合中，将X从集合中分离出来
        if (opers[0] == 2) {
            int x = -1;

            for (int i = 0; i < operSets.size(); i++) {
                if (operSets[i].find(opers[1]) != operSets[i].end()) {
                    x = i;
                    break;
                }
            }

            // 整数X在集合数组中的某个集合中
            if (x > -1) {
                // 从该集合中删除该数
                operSets[x].erase(opers[1]);
            }

            // 无论是否存在某个集合中，该数都独自一个集合
            // 存入集合数组中
            unordered_set<int> tmpSet;
            tmpSet.insert(opers[1]);
            operSets.push_back(tmpSet);
        }

        // 输出整数X所在集合的整数个数
        if (opers[0] == 3) {
            int x = -1;

            for (int i = 0; i < operSets.size(); i++) {
                if (operSets[i].find(opers[1]) != operSets[i].end()) {
                    x = i;
                    break;
                }
            }

            if (x > -1) {
                ans.push_back(operSets[x].size());
            } else if (x == -1) {
                ans.push_back(1);
            }
        }
    }

    return ans;
}

int main() {
    int T;
    cin >> T;
    if (T < 1 || T > 5) {
        return 0;
    }

    vector<vector<int>> count;
    for (int k = 0; k < T; k++) {
        int N, M;
        cin >> N >> M;

        if (N < 1 || N > 10000 || M < 1 || M > 1000) {
            return 0;
        }

        vector<vector<int>> operations;

        for (int i = 0; i < M; i++) {
            vector<int> opers;
            int flag = 0;
            cin >> flag;
            if (flag > 3 || flag < 0) {
                return 0;
            }

            opers.push_back(flag);
            if (flag == 1) {
                int X, Y;
                cin >> X >> Y;
                if (X < 1 || X > N || Y < 1 || Y > N) {
                    return 0;
                }

                opers.push_back(X);
                opers.push_back(Y);
            } else if (flag == 2 || flag == 3) {
                int X;
                cin >> X;
                if (X < 1 || X > N) {
                    return 0;
                }

                opers.push_back(X);
            }

            operations.push_back(opers);
        }

        vector<int> ans = retCount(operations);
        count.push_back(ans);
    }


    for (const auto &cou : count) {
        for (auto c : cou) {
            cout << c << endl;
        }
    }

    return 0;
}