1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+5;
int n,m;
int tmp[MAXN];
int rd[MAXN],cd[MAXN];
stack<int> st;
vector<int> G[MAXN];
void dfs(int S)
{
for(int i=tmp[S];i<G[S].size();i=tmp[S])
tmp[S]=i+1,dfs(G[S][i]);
// tmp[S] : G[S][1,2,...,tmp[S]-1] 都已访问,下一次从 G[S][tmp[S]] 开始
st.push(S);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1,u,v;i<=m;i++)
{
scanf("%lld%lld",&u,&v);
G[u].push_back(v); // 注意有向图
cd[u]++,rd[v]++;
}
for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
int S=1,c1=0,c2=0;
bool flg=1; // 是否所有点出入度相等
for(int i=1;i<=n;i++)
{
if(cd[i]!=rd[i])
{
flg=0;
if(cd[i]-rd[i]==1) c1++,S=i; // 出度比入度大 1
else if(rd[i]-cd[i]==1) c2++;
else return puts("No"),0;
}
}
if(flg==0&&!(c1==c2&&c1==1))
return puts("No"),0; // 不满足判定条件
dfs(S);
while(!st.empty())
printf("%lld ",st.top()),st.pop();
return 0;
}
|