将所有点的深度求出后对相邻深度选择较大的保留

$O(\sum{(n+m)})$ TLE on #2

#2 是 $T=2*10^5$，所有询问都是 0 1。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x = 0,h = 1;
	char ch = getchar();
	while(!(ch=='-'||('0'<=ch&&ch<='9'))) ch = getchar();
	if(ch=='-') h = -1;
	else x = ch-'0';
	ch = getchar();
	while('0'<=ch&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*h;
}
void write(ll x){
	if(x>9){
		write(x/10);
		x%=10;
	}
	putchar(x+'0');
}
const ll N = 200010;
ll n,m,mlx = 0;
ll rd[N];
bool vis[N];
bool res[N];
ll dep[N],siz[N];
vector<ll> ans;
struct Edge{
	ll to;
	ll val;
};
vector<Edge> vec[N];
void dfs(ll id,ll depth){
	vis[id] = true;
	dep[id] = depth;
	mlx = min(mlx,dep[id]);
	for(auto u : vec[id]){
		ll v = u.to;
		if(vis[v]) continue;
		dfs(v,depth+u.val);
	}
}
int main(){
	//freopen("_.in","r",stdin);
	//freopen("__.out","w",stdout);
	ll T = read();
	while(T--){
		n = read();m = read();
		if(n<=2){
			puts("0");
			continue;
		}
		//
		for(ll i = 1; i <= n; i++) vec[i].clear();
		memset(dep,0,sizeof(dep));memset(siz,0,sizeof(siz));
		memset(vis,0,sizeof(vis));memset(res,0,sizeof(res));
		memset(rd,0,sizeof(rd));mlx = 0;
		ans.clear();
		//
		for(ll i = 1; i <= m; i++){
			ll u = read(),v = read();
			rd[v]++;
			vec[u].push_back((Edge){v,1});
			vec[v].push_back((Edge){u,-1});
		}
		for(ll i = 1; i <= n; i++){
			if(rd[i]==0){
				dfs(i,0);
			}
		}
		for(ll i = 1; i <= n; i++){
			//printf("dep[%lld]=%lld\n",i,dep[i]);
			siz[dep[i]-mlx]++;
		}
		for(ll i = 0; siz[i]; i+=2){
			if(siz[i+1]==0) continue;
			if(siz[i]<siz[i+1]){
				res[i] = true;
			} else {
				res[i+1] = true;
			}
		}
		for(ll i = 1; i <= n; i++){
			if(res[dep[i]-mlx]) ans.push_back(i);
		}
		printf("%lld\n",ans.size());
		if(ans.size()==0) continue;
		for(auto v : ans) printf("%lld ",v);
		if(ans.size()) puts("");
	}
	return 0;
}