题目链接

题目大意

贵族i有一个自己的权力a[i]，默认a[i]=i。

定义：一个贵族是脆弱的，当且仅当他有朋友&&他的所有朋友的权利都比他大。

n个点，m条边（朋友关系）。给定q次操作，每次操作有如下几种方式：

1. 添加u和v的朋友关系
2. 删除u和v的朋友关系
3. 进行一次查询

查询过程：把所有脆弱的贵族“杀死”，同时意味着断掉他的“朋友关系”，然后可能会有贵族因为别的贵族死亡而变得脆弱，然后再“杀死”这些脆弱的贵族……重复上述过程，直至没有脆弱的贵族，输出此时贵族的人数。

注意，在查询过后，“杀死”的贵族会“复活”，朋友关系也会继续存在。

解题思路

由于上述的过程十分类似于拓扑排序，因此我赛场上首先想到拓扑排序，但是由于自己水平过菜（想得太多&&代码实现能力过差）前后写了200多行也没搞出来。

其实可以用到拓扑序的思想，记录每个点的入度和出度。当一个贵族的朋友比他权力低，视作从低权力向高权力连一条有向边。低权力贵族的出度++，高权力贵族的入度++。删边同理

而实际上什么时候这个贵族不是脆弱的只取决于出度（和入度无关）。当一个贵族的出度=0，意味着他没有权力比他大的朋友，因此他永远不会死。所以本题仅需考虑每个点的出度即可。

千万不要考虑入度……因为无论入度是否等于0，只要出度大于0都会被最后消灭掉。

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
int T,t;
int n,m,k;
int r[N],c[N];//入度 出度
int opt;
int ans;

signed main(){
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    T=1;
    while(T--){
        cin>>n>>m;
        int u,v;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            if(u>v) swap(u,v);
            r[v]++;
            c[u]++;
        }
        for(int i=1;i<=n;i++){
            if(c[i]==0) ans++;
        }
        cin>>t;
        while(t--){
            cin>>opt;
            if(opt==1){
                cin>>u>>v;
                if(u>v) swap(u,v);
                r[v]++;
                c[u]++;
                if(c[u]==1) ans--;
            }
            if(opt==2){
                cin>>u>>v;
                if(u>v) swap(u,v);
                r[v]--;
                c[u]--;
                if(c[u]==0) ans++;
            }
            if(opt==3){
                cout<<ans<<"\n";
            }
        }
    }
    return 0;
}