90分求优化
查看原帖
90分求优化
372172
Q__A__Q楼主2022/8/2 22:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int ll

const int maxn=5e5+10;
const int inf=1e9+7;
int n,m,ans,in[maxn],ou[maxn],head[maxn],to[maxn],nxt[maxn],tot,vis[maxn],s,q;
int cnt1,cnt2,cnt3;
stack<int> st;

struct node {
	int u,v;
} e[maxn];

inline void ins(int u,int v) {
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void dfs(int u) {
	int v;
	//cout<<u<<' ';
	for(int i=head[u]; i; i=nxt[i]) {
		if(vis[i]==0) {
			//v=to[i];
			vis[i]=1;
			dfs(to[i]);
		}
	}
	st.push(u);
}

inline bool cmp(node a,node b) {
	if(a.u==b.u) return a.v>b.v;
	return a.u<b.u;
}

signed main() {
	n=read(),m=read();
	for(int i=1; i<=m; ++i) {
		e[i].u=read(),e[i].v=read();
		ou[e[i].u]++,in[e[i].v]++;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1; i<=m; ++i)
		ins(e[i].u,e[i].v)/*,cout<<e[i].u<<' '<<e[i].v<<endl;*/;
	for(int i=1; i<=n; ++i) {
		if(in[i]==ou[i]+1) q=i,cnt1++;
		else if(in[i]==ou[i]-1) s=i,cnt2++;
		else if(in[i]==ou[i]) cnt3++;
		else if(abs(in[i]-ou[i])>1) {
			puts("No");
			return 0;
		} 
	}
//	cout<<cnt1<<cnt2<<cnt3<<endl;
	if(cnt1>1||cnt2>1) {
		puts("No");
		return 0;
	}
	if(cnt1+cnt2+cnt3!=n) {
		puts("No");
		return 0;
	} 
	if(cnt3==n) s=1;
	dfs(s);
	while(!st.empty()) {
		printf("%d ",st.top());
		st.pop();
	}
	return 0;
} 
2022/8/2 22:05
加载中...