60pts求调,悬棺
查看原帖
60pts求调,悬棺
1003842
Central_GYM楼主2023/10/11 22:28
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    register char ch;
    register int t=1,x=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            t=-1;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*t;
}
inline void write(int x){
    if(x<0){
        x=-x;
    }
    if(x>9){
    putchar(x%10+'0');
        write(x/10);
    }
}
struct node{
	int u,v;
}num[114514];
struct k{
	int cnt_son,cnt_father;
}check[100005];
vector<int> G[100005];
int path[200005];
int del[100005];
int n,m,cnt0,cnt1,root,tot_path;
bool cmp(node x,node y){
	if(x.u==y.u){
		return x.v<y.v;
	}
	return x.u<y.u;
}
void DFS(int now){
	for(int i=del[now];i<G[now].size();i=del[now]){
		del[now]=i+1;
		DFS(G[now][i]);
	}
	path[++tot_path]=now;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		num[i].u=read();
		num[i].v=read();
		check[num[i].u].cnt_son++;
		check[num[i].v].cnt_father++;
	}
	for(int i=1;i<=n;i++){
		if(abs(check[i].cnt_son-check[i].cnt_father)>1){
			printf("No");
			return 0;
		}
		if(check[i].cnt_son-check[i].cnt_father==1){
			cout<<i<<endl;
			cnt0++;
			root=i;
		}if(check[i].cnt_son-check[i].cnt_father==-1){
			cnt1++;
		}
	}
	if((cnt0==0&&cnt1==0)||(cnt0==1&&cnt1==1)){
		sort(num+1,num+1+m,cmp);
		for(int i=1;i<=m;i++){
			G[num[i].u].push_back(num[i].v);
		}
		if(root==0){
			root=1;
		} 
		DFS(root);
		for(int i=tot_path;i>=1;i--){
			cout<<path[i]<<' ';
		}
	}else{
		printf("No");
		return 0;
	}
	return 0;
}

WA了后四个点

2023/10/11 22:28
加载中...