题解：CF1037E Trips

· · 题解

CF1037E

入手

先考虑将问题简化， 如果只要求一天晚上的人数怎么做？
答案：重复将所有度数小于 k 的点去掉，并删除相邻的边，直到没有这样的点为止。

不难看出这是一个改版的拓扑排序。

解法

通过这样的方法，我们就可以先求出最后一天的旅行人数。

考虑从 m 天到第 1 天倒着求，第 i-1 天就是在第 i 天的基础上断一条边，会有点的度数减小，方便我们做拓扑。

每次删边的时候，将连接的两个点度数减一。

程序设计

拓扑排序需要简单修改
我这边删除边是邻接表硬删（第 51 行）
我使用了函数 qingtui(x) 来删除一个点并加入拓扑的队列 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e5+10;
vector<int> to[N];
struct Edge{int u,v;}e[N];
int n,m,k,ans;
int d[N];// 度数
bool del[N];

queue<int> q;// 拓扑排序

void qingtui(int x){
    q.push(x);
    ans--;
    del[x]=1;
}

void topo(){
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v:to[u]){
            if(!del[v] && (--d[v])<k){
                qingtui(v);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[i]={u,v};
        to[u].push_back(v);
        to[v].push_back(u);
    }
    for(int i=1;i<=m;i++)d[e[i].u]++, d[e[i].v]++;

    ans=n;
    for(int i=1;i<=n;i++)if(d[i]<k)qingtui(i);
    topo();
    vector<int> output;
    output.push_back(ans);
    for(int i=m;i>=2;i--){
        int u=e[i].u, v=e[i].v;
        to[u].pop_back(); to[v].pop_back();
        if(!(del[u]||del[v])){// 这条边还没被拓扑排序删除掉
            if((--d[u])<k)qingtui(u);
            if((--d[v])<k)qingtui(v);

            topo();
        }
        output.push_back(ans);
    }
    reverse(output.begin(),output.end());
    for(int x:output)cout<<x<<"\n";
}