蒟蒻刚学OI 1ms 10pts 彩色评测结果求条
查看原帖
蒟蒻刚学OI 1ms 10pts 彩色评测结果求条
827873
abc1856896楼主2025/2/5 18:25
#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[200005],cnt;
struct data{
	int to;
	int next;
};
data edge[200005];
void add_edge(int from,int to) {
	cnt++;
	edge[cnt].to=to;
	edge[cnt].next=head[from];
	head[from]=cnt;
}
struct node {
	int u;
	int v;
};
node a[200005];
bool cmp(node t1,node t2) {
	if(t1.u!=t2.u) return t1.u<t2.u;
	else return t1.v>t2.v;
}
int n,m,in[100005],out[100005];
int st=1;
int en=0;
stack<int> ans;
bool vis[200005];
int hd[200005];
void dfs(int u) {
	//cout<<u<<" "<<hd[u]<<endl;
	for(int i=hd[u];i;i=edge[i].next) {
		//if(!vis[i]){
			int v=edge[i].to;
			vis[i]=1;
			hd[u]=edge[i].next;
			dfs(v);
		//}
	}
	ans.push(u);
}
int sum1,sum2;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		cin>>a[i].u>>a[i].v;
		in[a[i].v]++;
		out[a[i].u]++;
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++) {
		add_edge(a[i].u,a[i].v);
	}
	for(int i=1;i<=n;i++) {
		if(abs(in[i]-out[i])>1) {
			cout<<"No";
			return 0;
		}
		if(out[i]-in[i]==1) {
			st=i;
			sum1++;
		}
		if(in[i]-out[i]==1) {
			en=i;
			sum2++;
		}
	}
	if(sum1!=sum2) {
		cout<<"No";
		return 0;
	}
	//cout<<st<<" "<<en<<endl; 
	//for(int i=1;i<=m;i++) cout<<edge[i].to<<" "<<edge[i].next<<endl;
	//cout<<endl;
	for(int i=1;i<=n;i++) hd[i]=head[i];
	dfs(st);
	while(ans.size()) {
		cout<<ans.top()<<" ";
		ans.pop();
	}
	return 0;
}

WA on #1,#2,#3,#4,#5,#9

MLE on #7,#8,#10

AC on #6

2025/2/5 18:25
加载中...