P5022 旅行[基环树]

以后必须学会面向数据编程！看半天题目不知道咋写直接爆搜，结果分少的可怜，还不如直接贪搞个60分。

观察数据，发现图至多存在一个环。

显然，如果没有环，这个题不跟你多bb，直接贪就完事了，线性复杂度。

原因十分显然，一旦你还没走到底就往回走的话，就走不完整张图了。

有环的话，这题就是个基环树。

根据题意，小Y显然是不能走完一个环的，那就简单了，直接删边开搞。

参考代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<string>

#include<cstdlib>

#include<queue>

#include<vector>

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define N 5010

#define MOD 2520

#define E 1e-12

using namespace std;

inline int read()

{

	int f=1,x=0;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int n,m;

vector<int> g[N],ans,tmp;

int stack[N],top;

bool v[N],vis[N][N],flag;

inline void upd()

{

	for(int j=0;j<tmp.size();++j){

		if(tmp[j]>ans[j]) break;

		if(tmp[j]<ans[j]){

			ans.clear();

			for(int i=0;i<tmp.size();++i)

				ans.push_back(tmp[i]);

		}

	}

	tmp.clear();

}

inline void dfs2(int x,int fa)

{

	tmp.push_back(x);

	for(int i=0;i<g[x].size();++i){

		int y=g[x][i];

		if(y==fa||vis[x][y]) continue;

		dfs2(y,x);

	}

}

inline void dfs1(int x,int fa)

{

	v[x]=1;stack[++top]=x;

	for(int i=0;i<g[x].size();++i){

		int y=g[x][i];

		if(y==fa) continue;

		if(v[y]){

			int tmp=stack[top];

			vis[tmp][y]=vis[y][tmp]=1;

			dfs2(1,0);

			vis[tmp][y]=vis[y][tmp]=0;upd();

			while(tmp!=y){

				int pre=stack[--top];

				vis[tmp][pre]=vis[pre][tmp]=1;

				dfs2(1,0);

				vis[tmp][pre]=vis[pre][tmp]=0;

				upd();tmp=pre;

			}

			for(int i=0;i<ans.size();++i)

				printf("%d ",ans[i]);

			exit(0);

		}

		else dfs1(y,x);top--;

	}

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=m;++i){

		int u=read(),v=read();

		g[u].push_back(v),g[v].push_back(u);

	}

	for(int i=1;i<=n;++i) sort(g[i].begin(),g[i].end());

	ans.push_back(INF);

	dfs1(1,0);

	if(!flag) dfs2(1,0);upd();

	for(int i=0;i<ans.size();++i)

		printf("%d ",ans[i]);

	return 0;

}