题解

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<int>> adj;
vector<int> answers;

void dfs(int a, int time) {
    if (answers[a] == 0) {
        answers[a] = time;
        for (int b : adj[a]) {
            dfs(b, time);
        }
    }
}

struct Edge {
    int from;
    int to;
};

int main() {
    int n, q;
    cin >> n >> q;

    adj.resize(n + 1);
    answers.resize(n + 1);

    set<int> alwaysActive;
    for (int a = 1; a <= n; a++) {
        alwaysActive.insert(a);
    }

    vector<Edge> added;
    vector<Edge> removed(q);
    vector<int> deactivated(q);

    for (int j = 0; j < q; j++) {
        char type;
        cin >> type;

        if (type == 'D') {
            int a;
            cin >> a;
            deactivated[j] = a;
            alwaysActive.erase(a);
        } else if (type == 'A') {
            int a, b;
            cin >> a >> b;
            added.push_back({a, b});
        } else {
            int k;
            cin >> k;
            removed[j] = added[k - 1];
            added[k - 1] = {0, 0};
        }
    }

    for (const Edge& edge : added) {
        if (edge.from != 0 && edge.to != 0) {
            adj[edge.from].push_back(edge.to);
            adj[edge.to].push_back(edge.from);
        }
    }

    for (int a : alwaysActive) {
        dfs(a, q);
    }

    for (int j = q - 1; j > 0; j--) {
        if (deactivated[j] != 0) {
            dfs(deactivated[j], j);
        } else if (removed[j].from != 0 && removed[j].to != 0) {
            int a = removed[j].from;
            int b = removed[j].to;
            adj[a].push_back(b);
            adj[b].push_back(a);
            if (answers[a] != 0 || answers[b] != 0) {
                dfs(a, j);
                dfs(b, j);
            }
        }
    }

    for (int a = 1; a <= n; a++) {
        cout << answers[a] << endl;
    }

    return 0;
}