wa10分求助/kk

评测记录

#include<stdio.h>
#include<queue>
int a[300002],b[300002],fa[300001],v[600001],nxt[600001],head[300001],tot,degree[300001],ans[300001];
inline void link(int a,int b){v[++tot]=b,nxt[tot]=head[a],head[a]=tot;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
bool merge(int x,int y){
	int rx=find(x),ry=find(y);
	if(x==y)return true;
	return fa[rx]=ry,false;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=q;++i){
		int s,t;
		scanf("%d%d",&s,&t);
		if(s==t)continue;
		if(s<t)++a[s+1],--a[t+1];
		else++b[t],--b[s];
	}
	for(int i=1;i<=n;++i)fa[i]=i;
	int x=a[0],y=b[0];
	for(int i=1;i<=n;++i){
		x+=a[i],y+=b[i];
		if(x&&i-2>0){link(i,i-2);if(merge(i,i-2))return puts("QED"),0;}
		if(y&&i+2<=n){link(i,i+2);if(merge(i,i+2))return puts("QED"),0;}
	}
	std::priority_queue<int,std::vector<int>,std::greater<int> > Q;
	for(int i=1;i<=n;++i)for(int j=head[i];j;j=nxt[j])++degree[v[j]];
	for(int i=1;i<=n;++i)if(!degree[i])Q.push(i);
	int cnt=0;
	for(;Q.size();){
		int x=Q.top();Q.pop();
		ans[x]=++cnt;
		for(int j=head[x];j;j=nxt[j])if(!(--degree[v[j]]))Q.push(v[j]);
	}
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	return 0;
}