这里引入一个概念：k-核(k-Core)。

在一个无向图中，$k$-核是删去所有度数小于 $k$ 的顶点，不断迭代，剩下的最大子图。

此题中，训练的参与者集必须是当日图中的一个 $k$-核。要让参与人数尽可能多，则自然取整张图的$k$-核。

如果我们直接模拟每天增加一条边后都重新跑一次 $k$-核（$bfs$删除度$＜k$ 的顶点），最坏每次都要 $O(n+m)$，总共也就是 $O((n+m)m)$，会超时。

所以采用算法竞赛中很常用的一个思想：正难则反。

将「每天加一条边」的问题，倒过来想成：「从全图开始，逐天『删掉』一条边」，并动态维护 $k$-核的大小。具体做法：

• 首先，将$m$条边全部加到图上，并将这$m$条边都按顺序存到一个数组里。
• 然后开始求全图的$k$-核：
  • 首先，在存图的时候要记录每个点的度数$d[u]$
  • 然后，开一个队列，将所有入度$<k$的点入队，逐个将这些点弹出队列。
  • 在弹出队列的过程中，遍历这些点的出边，将这些边标记“失效”，并将这些边的终点的度数$-1$，如果某个终点的度数由$k$减到了$k - 1$，将其入队。
• 循环直到队列为空。
• 剩下的点和边，即为全图的$k$核。

然后，逆序遍历你存边的数组，一条一条删边，删边时给两个端点入度$-1$，如果某个点的度数由$k$减到了$k - 1$，给它入队，重复上面的步骤，队列为空后用一个答案数组存现在剩下的点数。

这样倒序得到的答案数组，正好是正序中每一天晚上的最大参与人数。

当然，如果你不想在前面先写一遍求$k$-核的话，那你也可以将队列改成用$vector$来模拟队列的过程。

时间复杂度：$O(n+ m)$

ACcode1

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<PII>> g(n + 1);
    vector<PII> edges(m + 1);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    vector<bool> st_edge(m + 1, true);
    vector<bool> st_node(n + 1, true);
    vector<int> deg(n + 1);
    queue<int> q;
    for(int i = 1; i <= n; i++){
        deg[i] = g[i].size();
        if(deg[i] < k){
            st_node[i] = false;
            q.push(i);
        }
    }
    int cnt = n;
    while(!q.empty()){
        int u = q.front(); q.pop();
        cnt--;
        for(auto &e : g[u]){
            int v = e.first, id = e.second;
            if(st_node[v] && st_edge[id]){
                if(--deg[v] == k - 1){
                    st_node[v] = false;
                    q.push(v);
                }
            }
        }
    }
    vector<int> res(m + 1, 0);
    for(int i = m; i >= 1; i--){
        res[i] = cnt;
        int u = edges[i].first;
        int v = edges[i].second;
        if(st_edge[i]){
            st_edge[i] = false;
            if(st_node[u] && st_node[v]){
                if(--deg[u] == k - 1){
                    st_node[u] = false;
                    q.push(u);
                }
                if(--deg[v] == k - 1){
                    st_node[v] = false;
                    q.push(v);
                }
                while(!q.empty()){
                    int u = q.front(); 
                    q.pop();
                    cnt--;
                    for(auto &e : g[u]){
                        int v = e.first, id = e.second;
                        if(st_node[v] && st_edge[id]){
                            if(--deg[v] == k - 1){
                                st_node[v] = false;
                                q.push(v);
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= m; i++){
        cout << res[i] << endl;
    }
    return 0;
}

ACcode2

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<PII>> g(n + 1);
    vector<PII> edges(m);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        g[u].push_back({v, i}), g[v].push_back({u, i});
    }
    vector<bool> st(m + 1, true);
    vector<int> deg(n + 1);
    vector<int> q;
    for(int i = 1; i <= n; i++){
        deg[i] = g[i].size();
        if(deg[i] < k){
            q.push_back(i);
        }
    }
    vector<int> res(m);
    int cnt = 0;
    for(int i = m - 1; i >= 0; i--){
        while(cnt < (int) q.size()){
            int u = q[cnt];
            for(auto &e : g[u]){
                int v = e.first, id = e.second;
                if(!st[id]) continue;
                st[id] = false;
                if(deg[v] == k) q.push_back(v);
                deg[u]--, deg[v]--;
            }
            cnt++;
        }
        res[i] = n - (int)q.size();
        if(st[i]){
            int u = edges[i].first, v = edges[i].second;
            if(deg[u] == k) q.push_back(u);
            if(deg[v] == k) q.push_back(v);
            deg[u]--, deg[v]--;
            st[i] = false;
        }
    }
    for(int i = 0; i < m; i++){
        cout << res[i] << endl;
    }
    return 0;
}