[ABC302E] Isolation 题解

FReQuenter · 2023-05-22 19:39:53 · 题解

我们可以使用 map 记录点 u 和点 v 是否有边，命名为 mp。对于答案，我们维护一个变量 s，表示独立的点的数量。初值为 n。

对于操作 1：我们只需要将 mp[u][v] 和 mp[v][u] 都设为 1。如果操作前 mp[u] 为空，则 s 减 1；如果操作前 mp[v] 为空，则 s 再减 1；

对于操作 2：我们一一将它周围的点 （设为 u）去掉当前点（设为 v），即 mp[u][v]=0,mp[v].clear()。答案统计一下周围点变成孤立点的数量。别忘了当前点。

复杂度分析：每一次操作 2 执行的数量都是到上一次操作 2 之间执行的操作 1 的数量，所以相当于执行了 2 倍操作 1，则时间复杂度 O(2n \log n)=O(n \log n)。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
map<int,bool> mp[300005];
signed main(){
    int n,q;
    cin>>n>>q;
    int sum=n;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int u,v;
            cin>>u>>v;
            if(!mp[u].size()) sum--;
            if(!mp[v].size()) sum--;
            mp[u][v]=1;
            mp[v][u]=1;
        }
        else{
            int v;
            cin>>v;
            if(mp[v].size()) sum++;
            for(auto nx:mp[v]){
                mp[nx.fi].erase(v);
                if(!mp[nx.fi].size()) sum++;
            }
            mp[v].clear();
        }
        cout<<sum<<'\n';
    }
}