CF1037E. Trips

题目链接

CF1037E. Trips

题解

每次删点后,对不满足要求的点拓扑

代码

#include<map>

#include<queue>

#include<vector>

#include<cstdio>

#include<algorithm>

#define rep(a,b,c) for(int a = b;a <= c;++ a)

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

void print(int x) {

	if(x < 0) {

		pc('-');

		x = -x;

	}

	if(x >= 10) print(x / 10);

	pc(x % 10 + '0');

}

const int maxn = 5000007;

int n,m,k;

int d[maxn];

bool del[maxn];

using namespace std;

#define pr pair<int,int>

#define mmp make_pair

map<pr,int> mp;

struct node {

	int v,next;

} edge[maxn];

int head[maxn],num = 0;

inline void add_edge(int u,int v) {

	edge[++ num].v = v; edge[num].next = head[u];head[u] = num;

}

int ans;

int u[maxn],v[maxn];

int Ans[maxn];

queue<int>q;

void solve(int x) {

	if(d[x] >= k || del[x]) return;

	del[x] = 1;

	q.push(x);

	ans --;

	while(!q.empty()) {

		int U = q.front();

		q.pop();

		for(int i = head[U];i;i = edge[i].next) {

			int V = edge[i].v;

			if(del[V]) continue;

			if(mp.count(mmp(U,V)) == 0) d[V] --;

			if(d[V] < k) { del[V] = true;ans --; q.push(V);}

		}

	}

}

int main() {

	n = read(),m = read(); k = read();

	rep(i,1,m) {

		u[i] = read(),v[i] = read();

		add_edge(u[i],v[i]);

		add_edge(v[i],u[i]);

		d[v[i]] ++;

		d[u[i]] ++;

	}

	ans = n;

	rep(i,1,n)

		solve(i);

	mp.clear();

	for(int i = m;i >= 1;-- i) {

		Ans[i] = ans;

		if(!del[u[i]]) d[v[i]] -- ;

		if(!del[v[i]]) d[u[i]] -- ;

		mp[pr(u[i],v[i])] = 1;

		mp[pr(v[i],u[i])] = 1;

		solve(u[i]);

		solve(v[i]);

	}

	rep(i,1,m)print(Ans[i]),pc('\n');

}

/*

500 2 3

58 102

250 411

*/