拍了两天了,没拍出问题,链式前向星
查看原帖
拍了两天了,没拍出问题,链式前向星
213196
Wens楼主2021/9/15 21:41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=1e5+1;
const int Maxm=2e5+1;

inline ll Read(){
	ll x=0;bool w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}

inline void Write(ll x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)Write(x/10);
	putchar(x%10+'0');
	return ;
}

struct node {
	int u,v;
}edge[Maxn];

int n,m,root=1;
int nxt[Maxm],head[Maxn],to[Maxm],tot;
int in[Maxn],out[Maxn];
int ans[Maxm],cnt;
bool vis[Maxm];

bool cmp1(node a,node b){return a.v>b.v;}

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

inline void dfs(int u){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(vis[i])continue;
		vis[i]=true;
		dfs(v);
	}
	ans[++cnt]=u;
}

int main(){
//	freopen("P7771.in","r",stdin);
//	freopen("P7771.out","w",stdout);
	n=Read(),m=Read();
	for(int i=1;i<=m;++i){
		edge[i].u=Read();
		edge[i].v=Read();
		++in[edge[i].v];
		++out[edge[i].u];
	}
	sort(edge+1,edge+1+m,cmp1);
	for(int i=1;i<=m;++i){
		int u=edge[i].u,v=edge[i].v;
		add(u,v);
	}
	bool flag1=1;
    int sum1=0,sum2=0;
    for(int i=1;i<=n;i++){
        if(out[i]!=in[i]){
            flag1=0;
        } 
        if(out[i]-in[i]>1){
            cout<<"No";
            return 0;
        }
        if(out[i]-in[i]==1){
            root=i;
            sum1++; 
        }
        if(in[i]-out[i]==1){
            sum2++; 
        }
    }
    if(!(flag1==1||(sum1==sum2)&&sum1==1)){
        cout<<"No";
        return 0;
    }
	dfs(root);
	for(int i=cnt;i>=1;--i){
		Write(ans[i]);
		putchar(' ');
	}
	putchar('\n');
	return 0;
}
2021/9/15 21:41
加载中...