Sample in
6 6
1 3
2 3
2 5
3 4
4 5
4 6
Sample out
1 3 2 4 5 6
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define maxn 5001
using namespace std;
vector<int> to[maxn];
int dfn[maxn],fa[maxn],tot,s;
bool inloop[maxn];
pair<int,int> del1,del2;
int n,m;
int ans[maxn],path[maxn],d;
map<pair<int,int>,bool> use;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
//基环树的情况
void dfs_getloop(int u){
dfn[u]=++tot;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(!dfn[v]) fa[v]=u,dfs_getloop(v);
else if(dfn[u]<dfn[v]){
inloop[v]=true;
do{ inloop[fa[v]]=true,v=fa[v]; }while(v!=u);
}
}
}
void dfs(int u,int pre){
path[++d]=u;
if(inloop[u]&&!s) s=u;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(v==pre||v==s) continue;
if(make_pair(u,v)==del1||make_pair(u,v)==del2) continue;
dfs(v,u);
}
}
inline void cmp(){//比较答案
for(register int i=1;i<=n;i++){
if(path[i]<ans[i]) break;
if(path[i]>ans[i]) return;
}
for(register int i=1;i<=n;i++) ans[i]=path[i];
}
//树的情况
void dfs2(int u,int pre){
ans[++d]=u;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(v==pre) continue;
dfs2(v,u);
}
}
int main(){
n=read(),m=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read();
to[u].push_back(v),to[v].push_back(u);
}
//按字典序排序,实际上这里用基排可以做到O(N)
for(register int i=1;i<=n;i++) sort(to[i].begin(),to[i].end());
if(m==n){
dfs_getloop(1);
memset(ans,0x3f,sizeof ans);
for(register int i=1;i<=n;i++) if(inloop[i]){
for(register int j=0;j<to[i].size();j++){
int v=to[i][j];
if(inloop[v]&&!use[make_pair(i,v)]){
d=s=0,del1=make_pair(i,v),del2=make_pair(v,i);//断掉双向边
use[make_pair(i,v)]=true,use[make_pair(v,i)]=true;//这里用map记一下可以把我们的遍历次数减半
dfs(1,0),cmp();
}
}
}
}else dfs2(1,0);
for(register int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
return 0;
}
\[ O(N*\sum_{i=1}^{N}log_{2}Degree[i]) \]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define maxn 500001
using namespace std;
vector<int> to[maxn];
int dfn[maxn],fa[maxn],tot;
bool inloop[maxn],vis[maxn],flag;
int n,m;
int ans[maxn],d;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
void dfs_getloop(int u){
dfn[u]=++tot;
for(register int i=0;i<to[u].size();i++){
int v=to[u][i];
if(!dfn[v]) fa[v]=u,dfs_getloop(v);
else if(dfn[u]<dfn[v]){
inloop[v]=true;
do{ inloop[fa[v]]=true,v=fa[v]; }while(v!=u);
}
}
}
void dfs(int u,int fa,int pre){
if(vis[u]) return;
ans[++d]=u,vis[u]=true;
priority_queue< int,vector<int>,greater<int> > q;
for(register int i=0;i<to[u].size();i++) if(!vis[to[u][i]]||to[u][i]!=fa) q.push(to[u][i]);
//换成这种写法的原因是为了更好地判断环上的下一个点不是自己的父亲
while(q.size()){
int v=q.top(); q.pop();
if(inloop[v]&&v>pre&&!q.size()&&!flag){ flag=true; return; }
if(inloop[v]&&q.size()) dfs(v,u,q.top());
else dfs(v,u,pre);
}
}
int main(){
n=read(),m=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read();
to[u].push_back(v),to[v].push_back(u);
}
if(m==n) dfs_getloop(1);
dfs(1,0,0x3f3f3f3f);
for(register int i=1;i<=n;i++){
if(i!=1) putchar(' ');
printf("%d",ans[i]);
}
return 0;
}
原文:https://www.cnblogs.com/akura/p/10939812.html