Codeforces Round #736 (Div. 2)_C. Web of Lies

C. Web of Lies

題目傳送門：

題目傳送門

題目截圖：

題目大意：

給你一張圖，連邊代表兩個點是朋友。一個點如果它所有的朋友都比它大，那他就出局了。接下來做q個操作：

1 u v

代表uv之間連邊；

2 u v

代表uv之間删邊；

3

表示輸出此時尚未出局的點數。

思路：

面向樣例程式設計。

得到兩個關鍵資訊：

1. 出局的點也可以繼續連邊邊；
2. 哈哈題目有給提示！

   

   意思就是隻要有連邊就會有人出局，隻要不是孤立點就會有機會被淘汰，除非是最強者，否則都會逐個淘汰。

代碼：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;;
int vis[maxn];

int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    int x, y;
    while (m--) {
        cin >> x >> y;
        if (x > y) {
            if (vis[y]) cnt++;
            vis[y]++;
        }
        if (y > x) {
            if (!vis[x]) cnt++;
            vis[x]++;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        if (k == 1) {
            int x, y;
            cin >> x >> y;
            if (x > y) {
                if (!vis[y]) cnt++;
                vis[y]++;
            }
            if (y > x) {
                if (!vis[x])cnt++;
                vis[x]++;
            }
        } else if (k == 2) {
            cin >> x >> y;
            if (x > y) {
                vis[y]--;
                if (!vis[y]) cnt--;
            } else {
                vis[x]--;
                if (!vis[x]) cnt--;
            }
        } else cout << n - cnt << endl;
    }
}