CF1037E Trips

/**
 * @Date:   2019-04-14T10:03:39+08:00
 * @Last modified time: 2019-04-14T10:03:39+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
int ans, n, m, k, del[A], in[A], a[A], b[A], out[A];
map<pair<int, int>, bool> mm;
void work(int x) {
    queue<int> q; q.push(x);
    if (in[x] >= k or del[x]) return;
    del[x] = 1; ans--;
    while (!q.empty()) { //踢出能遍历到的所有不符合条件的点
        int fr = q.front(); q.pop();
        for (int i = head[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            if (del[ca]) continue;
            if (!mm[make_pair(fr, ca)]) in[ca]--;
            if (in[ca] < k) {ans--; q.push(ca); del[ca] = 1;}
        }
    }
}

int main(int argc, char const *argv[]) {
    cin >> n >> m >> k; ans = n;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        add(a[i], b[i]); add(b[i], a[i]);
        in[a[i]]++; in[b[i]]++;
    }
    for (int i = 1; i <= n; i++) work(i);
    for (int i = m; i >= 1; i--) {
        out[i] = ans;
        if (!del[a[i]]) in[b[i]]--;
        if (!del[b[i]]) in[a[i]]--;
        mm[make_pair(a[i], b[i])] = mm[make_pair(b[i], a[i])] = 1;
        work(a[i]); work(b[i]);
    }
    for (int i = 1; i <= m; i++) cout << out[i] << endl;
}