浅谈基环树

更好的阅读体验

定义

对于一个连通图图 $G$，如果其点数与边数相等，那我们便称它为一个基环树。

也就是说，在一棵树上加一条边，就形成了一棵基环树。

一般地，如果图 $G$ 不连通，其点数与边数相等，那么肯定就是若干个基环树的组合，称之为基环森林。

我们通常将基环树分为以下几类：

• 无向基环树：基环树由无向边连接。

• 内向基环树：基环树由有向边连接，每个节点出度都为 $1$。

• 外向基环树：基环树由有向边连接，每个节点入度都为 $1$。

不同的基环树，我们都有不同的处理方法，选对处理方法往往能够事半功倍，具体会在下面例题中讲到。

思路

对于一棵基环树的问题，我们通常有以下两种处理方法：

1. 我们将一棵基环树视为一个环上面挂了很多子树，然后分别处理每一个子树，将信息合并到在环上的根上，把一棵基环树问题转化为一个在环上的问题

2. 我们将一棵基环树视为一个多了一条边的树，可以先将这一边删掉，将其转化为树上问题，之后我们再考虑加上这条边造成的影响，将之前的结果加上影响即可

例题

P2607 [ZJOI2008] 骑士 link

题目大意

给出一个 $n$（$1 \le n \le 10^6$）个点的带点权的基环森林，求这个基环森林的最优独立集。

最优独立集：选出若干个点，使其两两之间没有连边，最大化这些点的点权和。

解题思路

我们将一个骑士和他痛恨的骑士连边，由于两者间只要选一个另一个就不能选，所以可以连无向边，因此这就构成了一个无向基环森林。

对于每一棵基环树，我们都求出它的最优独立集，最后相加即可。

现在我们先考虑思路 2。

首先，我们需要找到这棵基环树的环，将其上的一条边断掉，也就是说只需要求环上的一条边即可。

无向基环树找环需任选一点为根，进行 dfs，访问过的点都进行标记，直到经过一条边到达的点已经标记过，就说明这条边在环上，记录即可。

代码实现上有很多点要注意，由于存在二元环的情况，即父子之间成环，也就是说父子之间有两条边，我们删除环上一条边后，仍然可以通过第二条边到达父亲。

这说明我们不能使用点判断是否重复走，也就是不能使用 v != fa[v]，因为这样会导致 v 不能通过另一条边到达 fa[v]，所以需要通过边来判断，即走的这条边是否和上一条边相同。

具体地，我们使用链式向前星加边时对应双向边的编号是相邻的，这样我们就令编号从 $2$ 开始，使得边 i 的对应边即为 i ^ 1，再在 dfs 时记录上一次经过的边 pre，通过 (i ^ 1) != pre 判断是否经过是否经过上一次经过的边。（如果链式向前星一开始初始化为 $0$ 就不能让编号从 $0$ 开始，因为 $0$ 号会被认为是没有边）

同理，在之后的 dp 中，我们判断是否经过删除的那条边时也不能用点判断，要记录删除的边的编号通过边判断。

这样，记录了删除的边之后，确保每次不经过这条边，便可以开始树形 dp：

• 状态表示：$dp_{i,0/1}$ 表示以 $i$ 为根的子树内，不选/选 $i$ 号节点，其最大独立集的大小。
• 初始化：$dp_{i,0} = 0$，$dp_{i,1} = a_i$（$a_i$ 为 $i$ 的权值）
• 状态转移
  • 不选 $i$：则儿子无限制，即$$dp_{i,0} = \sum{\max(dp_{son,1},dp_{son,0})}$$
  • 选 $i$：则儿子都不能选，即$$dp_{i,1} = \sum{dp_{son,0}}$$
• 答案：$\max(dp_{root, 0},dp_{root, 1})$

最后考虑删除的边 $(u, v)$ 造成的影响。

删除后，有可能两者都选，不符合题意，因此我们要使其最多只选一个。

可以先钦定 $u$ 不选，以 $u$ 为根跑一遍 dp，再钦定 $v$ 不选，以 $v$ 为根跑一遍 dp，这使得至少有一个不选，最后我们合并两者的答案，$\max(dp_{u, 0}, dp_{v, 0})$ 即为答案。

另外，本题也可以使用思路 1，将每个子树 dp 后再在环上 dp，但很显然其实现难度大于思路 2，故不再赘述。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

struct edge
{
	int to, next;
} e[N << 1];

int n, tot = 2, ui, vi, ei;
int h[N], a[N];
ll dp[N][2], ans;
bool vis[N];

void add(int u, int v)
{
	e[tot].to = v;
	e[tot].next = h[u];
	h[u] = tot++;
}

void find_circle(int u, int pre)
{
	vis[u] = 1;
	for (int i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if ((i ^ 1) != pre)
		{
			if (vis[v])
			{
				ui = u, vi = v, ei = i | 1;
				continue;
			}
			find_circle(v, i);
		}
	}
}

void dfs(int u, int pre)
{
	dp[u][0] = 0, dp[u][1] = a[u];
	for (int i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if ((i ^ 1) != pre && (i | 1) != ei)
		{
			dfs(v, i);
			dp[u][0] += max(dp[v][0], dp[v][1]);
			dp[u][1] += dp[v][0];
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int v;
		cin >> a[i] >> v;
		add(i, v);
		add(v, i);
	}
	for (int i = 1; i <= n; i++)
	{
		if (vis[i])
		{
			continue;
		}
		find_circle(i, -1);
		dfs(ui, -1);
		ll tmp = dp[ui][0];
		dfs(vi, -1);
		ans += max(tmp, dp[vi][0]);
	}
	cout << ans << endl;
	return 0;
}

P4381 [IOI 2008] Island link

题目大意

给出一个 $n$（$2 \le n \le 10^6$）个点的带边权的基环森林，求所有基环树的直径之和。

直径：基环树中距离最远的两点间的距离。

解题思路

一棵树加上一条边后，其直径难以基于原来的直径算出，因此我们考虑思路 1。

先分类讨论，基环树的直径可以分为以下两种情况：

1. 直径不经过环（环上的边都不在直径上）：将所有的子树的直径求出取最大值即可。
2. 直径经过环（存在环上的边在直径上）：设 $u,v$ 为环上两点，那么直径一定能表示为 $d_u + d_v + dis(u, v)$，其中 $d_i$ 表示 $i$ 子树内离 $i$ 最远的点到 $i$ 的距离（该子树的最大深度），$dis(u, v)$ 表示 $u$ 和 $v$ 在环上的距离。

我们主要是要解决出下面那种情况。

同样是思路 1，一般有两种实现方式：树形 dp与拓扑排序，下面都会讲解。

法 1

建双向边，构成一个无向基环森林。

同样地，我们先找环，这一次我们需要求出具体的环，因为 $dis(u,v)$ 是由若干条边组成的，并且记录边我们拥有的信息更多，所以我们需要将所有的边都记录在数组中。

我们仍然采用 dfs，但由于要记录每一条边，实现会有些许不同。

• 我们记录其 $dfn$ 序以代替打标记，如果我们从 $u$ 走到了一个已经访问过的点 $v$，还需判断是否 $dfn_v > dfn_u$，这保证了我们只允许从前辈访问后辈的时候再记录环，否则环会被记录两遍（后辈访问前辈也会记录一遍）。
• 我们预处理数组 $pre_i$，表示 $i$ 是他的父亲由 $pre_i$ 这条边到达 $i$ 的，这使得当前辈 $u$ 经过一条边到一个已经访问过的后辈 $v$ 时，只需让 $v$ 一直沿着 $pre_i$ 走，边走边将 $pre_i$ 放入数组，直到到达 $u$ 就停止（特别地，我们可以将这条多出来的 $(u, v)$ 放在数组的 $0$ 号）。
• 找环时还应将所有环上的点进行标记，避免 dp 时跑到环上的其他点。

找到环上的所有边后，我们对这个环上的每个点，以其为根进行树形 dp，求出 $d_i$，顺便处理分类讨论的第一种情况，记第一种情况的最长直径为 $mx$，每次在更新 $d_i$ 前，令 $mx = \max(mx, d_i + d_{son} + w(i,son))$ 即可。

现在我们考虑处理这个环上问题，即对环上两点 $u,v$，求 $\max(d_u + d_v + dis(u, v))$。

可以破环成链复制一份后跑单调队列 dp，但这里介绍一个更加简单的方法。

我们仍然破环成链，记 $s_i$ 为前 $i$ 条边的前缀和，$l_i$、$r_i$ 为第 $i$ 条边的左端点和右端点，$len$ 为环的长度。

那么最大值可以分为以下两种情况：

$$res1 = \max(d_{l_i} + d_{l_j} + s_i - s_j) = \max(d_{l_j} - s_j) + d_{l_i} + s_i$$$$res2 = \max(d_{l_i} + d_{l_j} + len - (s_i - s_j)) = \max(d_{l_j} - s_j) + d_{l_i} + len - s_i$$

由于我们是枚举 $i$ 的，可以将一些常值提出，也就是说我们只需预处理 $\max(d_{l_j} - s_j)$、$\max(d_{l_j} - s_j)$ 加上即可以做到 $O(n)$ 复杂度。

答案即为 $\max(mx, res1, res2)$。

法 2

我们只连单向边，构成一个内向基环森林。

然后我们进行拓扑排序，将度为 $0$ 的点放入队列，之后就按拓扑排序的方式走，出队后用自身信息更新父亲节点，然后进行标记。

可以发现，只有环上的点不会进入队列，也就是不会被标记，并且通过拓扑排序我们已经将子树的信息都合并到的环上，最后我们只剩下了若干个环需要处理。

接着对每个环计算第二种情况的结果即可，法 1 中已经提到了。

可以看到，拓扑排序是一种很好的处理基环树问题的方法，其码量要小于前者。

代码实现

法 1

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

struct edge
{
	int from, to, w, next;
} e[N << 1];

int n, tot = 2;
int h[N], pre[N];
int dfn[N], dfc;
bool vis[N];
int lp[N], cnt;
ll ans, mx, d[N], s[N];

void add(int u, int v, int w)
{
	e[tot].from = u;
	e[tot].to = v;
	e[tot].w = w;
	e[tot].next = h[u];
	h[u] = tot++;
}

void find_circle(int u)
{
	dfn[u] = ++dfc;
	for (int i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if ((i ^ 1) == pre[v])
		{
			continue;
		}
		if (!dfn[v])
		{
			pre[v] = i;
			find_circle(v);
			continue;
		}
		if (dfn[v] < dfn[u])
		{
			continue;
		}
		vis[v] = 1;
		lp[0] = i ^ 1;
		while (v != u)
		{
			lp[++cnt] = pre[v];
			vis[e[pre[v]].from] = 1;
			v = e[pre[v]].from;
		}
	}
}

void dfs(int u)
{
	vis[u] = 1;
	for (int i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to, w = e[i].w;
		if (!vis[v])
		{
			dfs(v);
			mx = max(mx, d[u] + d[v] + w);
			d[u] = max(d[u], d[v] + w);
		}
	}
}

ll solve(int x)
{
	mx = dfc = cnt = 0;
	find_circle(x);
	dfs(e[lp[0]].from);
	ll len = e[lp[0]].w;
	for (int i = 1; i <= cnt; i++)
	{
		dfs(e[lp[i]].from);
		s[i] = s[i - 1] + e[lp[i]].w;
	}
	len += s[cnt];
	ll res1 = -1e18, res2 = -1e18, mx1 = -1e18, mx2 = -1e18;
	for (int i = 1; i <= cnt; i++)
	{
		mx1 = max(mx1, d[e[lp[i]].to] - s[i - 1]);
		mx2 = max(mx2, d[e[lp[i]].to] + s[i - 1]);
		res1 = max(res1, mx1 + d[e[lp[i]].from] + s[i]);
		res2 = max(res2, mx2 + d[e[lp[i]].from] - s[i]);
	}
	return max(mx, max(res1, res2 + len));
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int v, w;
		cin >> v >> w;
		add(i, v, w);
		add(v, i, w);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			ans += solve(i);
		}
	}
	cout << ans << endl;
	return 0;
}

法 2

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e6 + 10;

int n;
int fa[N], w[N], deg[N];
queue<int> q;
ll d[N], dp[N], ans;

void topo()
{
	for (int i = 1; i <= n; i++)
	{
		if (!deg[i])
		{
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		dp[fa[x]] = max(dp[fa[x]], max(dp[x], d[fa[x]] + d[x] + w[x]));
		d[fa[x]] = max(d[fa[x]], d[x] + w[x]);
		if (!(--deg[fa[x]]))
		{
			q.push(fa[x]);
		}
	}
}

ll solve(int x)
{
	ll len = w[x], res1 = dp[x], res2 = -1e18, mx1 = d[x], mx2 = d[x];
	int st = x;
	deg[x] = 0;
	x = fa[x];
	while (x != st)
	{	
		deg[x] = 0;
		res1 = max(res1, max(dp[x], d[x] + len + mx1));
		res2 = max(res2, d[x] - len + mx2);
		mx1 = max(mx1, d[x] - len);
		mx2 = max(mx2, d[x] + len);
		len += w[x];
		x = fa[x];
	}
	return max(res1, res2 + len);
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> fa[i] >> w[i];
		deg[fa[i]]++;
	}
	topo();
	for (int i = 1; i <= n; i++)
	{
		if (deg[i])
		{
			ans += solve(i);
		}
	}
	cout << ans << endl;
	return 0;
}

P3472 [POI 2008] MAF-Mafia

题目大意

有 $n$（$1 \le n \le 10 ^ 6$）个人，每个人都用枪指着一个人（可以是自己），给出每个人用枪指着的人，之后按照需按照一定顺序开枪，求可能的最小和最大的死亡人数。

解题思路

每个人与他指着的人建单向边，形成一个内向基环森林。

由于思路 1 并不能很好地解释，我们仍然采取思路 2 的观点，即把基环树看作挂着许多子树的环。

我们先分析最大值，考虑一个环，最少只有一个人活下来（特别地，自环的话是可以全部死亡，需要特判）。

我们再考虑一棵树，叶子节点一定不死，因为没有人指着他们，然后如果想要更多人死，那就要尽可能在一个人死之前就开枪，于是我们可以从根的儿子先开始开枪，然后一层一层地开枪，最后只有叶子会活下来。

那么，结合两种观点，如果这个环上有子树的话，先让环开枪，最后只让这个有子树的点活下来，最后让所有子树按照层数开枪，环上的那个点会死掉，其他不是叶子的也会死，也就是这棵子树只有叶子活下来。

所以，最大值可以分三种情况：

• 自环：没人活。
• 环：活一个。
• 基环树：叶子活下来。

所有基环树存活数加起来，就能求得最小存活数，也就是最大死亡数。

我们再来分析最小值，根据上面的分析可以知道，叶子节点一定活下来。

递推可知，叶子节点的父亲必死，那么叶子节点的爷爷如果没有其他叶子指着就能活下来，然后一层层推广开来。

我们使用贪心思想，如果一个点是必死的，那我们绝对不让他在死前开枪，这一定是不优的，因为这个人的死亡最多能使其指向的点从死转到活，并不能使两个及以上的点由死到活以达到更优。

于是，我们可以发现活与死的等价条件：

• 活等价于是叶子或者指向他的点都死亡。
• 死等价于有活的点指向他。

基于这两个条件，我们可以采用递推的思想，一开始叶子的状态一定是确定的，然后让叶子去更新叶子父亲，叶子父亲去更新叶子爷爷，以此类推。

实现我们可以采取类似于拓扑排序的操作，先将度为 $0$ 的点也就是叶子入队，然后每次次取出队首，更新其指向点的信息：

• 队首状态是死：将其指向的点的入度减 $1$，如果其指向点入度为 $0$，就将其标记为活，入队。
• 队首状态是活：如果他指向的点状态不是死，也就是说他还没被打死，就将其标记为死，同时更新最小死亡数，入队（我们不去修改它的度数，因为这使得其度数绝对不会被减到 $0$，避免前面将其起死回生的情况）。

如此以来，最后还可能有一些状态没有确定的点，这些点只有可能是其中任何一个点都没有被标记必死的环（如果一个环有点被其儿子标上必死，那么这个环就被打开了一个缺口，最后整个基环树的状态都能被确定）。

所以，我们再便利所有点，如果这个点状态没有确定，就一直往其指着的点走，遍历这个环，并且都标记其状态，最后找出次环的长度，对于一个环，其最大存活数显然为 $\frac{len}{2}$，加上即可。

代码实现上，最小值可以和最大值一起处理，只需在进行拓扑排序时记录一个 $vis$ 表示此环有没有环外的子树，最后在遍历环时将所有 $vis$ 取或，为 $0$ 就说明此环没有子树，需要将最大死亡数减 $1$。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

int n, cnt;
int p[N], deg[N], st[N];
int ans1, ans2;
bool vis[N];
queue<int> q;

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	ans1 = ans2 = n;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
		deg[p[i]]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!deg[i])
		{
			ans1--, ans2--;
			st[i] = 1;
			vis[i] = 1;
			q.push(i);
		}
	}
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[p[x]] = 1;
		if (st[x] == 1)
		{
			if (st[p[x]] == 2)
			{
				continue;
			}
			st[p[x]] = 2;
			q.push(p[x]);
		}
		else
		{
			if (--deg[p[x]])
			{
				continue;
			}
			st[p[x]] = 1;
			q.push(p[x]);
			ans1--;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])
		{
			int len = 0;
			bool flag = 0;
			for (int j = i; !st[j]; j = p[j])
			{
				len++;
				flag |= vis[j];
				st[j] = 1;
			}
			ans1 -= len / 2;
			ans2 -= (flag ^ 1) && (len != 1);
		}
	}
	cout << ans1 << " " << ans2 << endl;
	return 0;
}

P10933 创世纪 link

题目大意

给出一个有向基环森林，选出若干点，要求所有选出的点都必须要有一个没被选出的点指向它，最大化选出点数。

解题思路

同样地，这道题也可以考虑思路 1，但是思路 2 还是更加简便。

这道题连边上有些文章可作，我们将集成内向基环树与外向基环树的优点，进行连边。

具体地，记 $u$ 指向 $v$，我们用数组 $p$ 记录一个点指向的点即 $p_u = v$，这是内向基环树；我们再用链式向前星由 $v$ 向 $u$ 建单向边，这是外向基环树。

这么连边的好处是操作方便，内向基环树优点是找环方便，由于点都是向内指的，只需随便选一个点一直往其指向的点走，直到重复为止便找到了环；而链式向前星建单向边的好处是方便 dp，删去环上一边后，以断点为根，每个节点其连边都是儿子。

上面已经说过了找环方法，将边断掉之后便可以开始树形 dp：

• 状态表示：$dp_{i,0/1}$ 表示在以 $i$ 根的子树内，$i$ 不选 / 选时的最大选点数。
• 初始化：$dp_{i,0/1}=0$
• 状态转移

  • 不选 $i$：则其子节点不受限制，即

    $$dp_{i,0}=\sum_{j \in son_i}{\max(dp_{j,0},dp_{j,1})}$$

  • 选 $i$：则其子节点至少有一个不选，即

    $$dp_{i,1}=1+\max_{j \in son_i}{(dp_{j,0}+\sum_{k \in son_i,k \neq j}{\max(dp_{k,0},dp_{k,1})})}$$

    复杂度较高，考虑优化，发现右边的和式与 $dp_{i,0}$ 很相似，于是有：

    $$\begin{aligned}dp_{i,1} &= 1+\max_{j \in son_i}{(dp_{j,0}+dp_{i,0} - \max(dp_{j,0},dp_{j,1}))} \\ &= 1 + dp_{i,0} - \min_{j \in son_i}{(\max(dp_{j,0},dp_{j,1}) - dp_{j,0})}\end{aligned}$$

    即可快速转移。

• 答案：$\max(dp_{rt,0},dp_{rt,1})$

现在我们考虑删去边的影响，原来有一条边是由根指向一个节点的，但是被删除了，这意味者原来根是可以限制此节点的，现在不行了，也就是说我们要考虑根限制此节点的情况。

于是我们再跑一遍 dp，钦定选根节点，即这个点已经被限制住了，意味着就算选这个点其儿子也不受任何限制，只需将选这个点的 dp 值加上 $\min_{j \in son_i}{(\max(dp_{j,0},dp_{j,1}) - dp_{j,0})}$ 即可，最后答案为 $dp_{rt,1}$，与上面得到答案取最大值便得到了最终答案。

代码实现

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e6 + 10;

struct edge
{
	int to, next;
} e[N];

int n, tot, rt, ans;
int a[N], h[N];
int dp[N][2];
bool vis[N];

void add(int u, int v)
{
	tot++;
	e[tot].to = v;
	e[tot].next = h[u];
	h[u] = tot;
}

void dfs(int u, bool flag)
{
	dp[u][0] = 0;
	vis[u] = 1;
	int mn = 1e9;
	for (int i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if (v != rt)
		{
			dfs(v, flag);
			dp[u][0] += max(dp[v][0], dp[v][1]);
			mn = min(mn, max(dp[v][0], dp[v][1]) - dp[v][0]);
		}
	}
	dp[u][1] = 1 + dp[u][0] - mn;
	if (flag && u == a[rt])
	{
		dp[u][1] += mn;
	}
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		add(a[i], i);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			for (rt = i; !vis[rt]; rt = a[rt])
			{
				vis[rt] = 1;
			}
			dfs(rt, 0);
			int tmp = max(dp[rt][0], dp[rt][1]);
			dfs(rt, 1);
			ans += max(tmp, dp[rt][0]);
		}
	}
	cout << ans << endl;
	return 0;
}

D30 基环树 P5022 [NOIP2018 提高组] 旅行

// 基环树 遍历最小字典序 O(nlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=500010;
int n,m,vis[N],path[N],fa[N],inc[N],yzd,cnt,tmp,yhs;
vector<int> e[N];

void dfs1(int x){ //树搜索
  vis[x]=1;
  path[++cnt]=x;
  for(int y:e[x])if(!vis[y]) dfs1(y);
}
void find(int x,int f){ //找环
  if(yzd) return;
  if(fa[x]){
    while(f!=x){
      inc[f]=1;
      f=fa[f];
    }
    inc[x]=1; //在环上
    yzd=1;    //已找到
    return;
  }
  fa[x]=f;
  for(int y:e[x]) if(y!=f) find(y,x);
}
void dfs2(int x){ //环树搜索
  vis[x]=1;
  path[++cnt]=x;
  if(inc[x]){ //x在环上
    int flag=0;
    for(int i=0;i<e[x].size();i++){ //枚举x的出边点
      if(yhs) break;
      int y=e[x][i];
      if(vis[y]) continue;
      if(inc[y]){ //y在环上
        i++;
        if(vis[e[x][i]]) i++; //跳过环的入口点
        if(i<e[x].size()) tmp=e[x][i]; //环点x的未访问的第一个出边点
        else if(y>tmp){ //环点y大于前面环点x的出边点，该回去访问了
          flag=1; //找到回溯点
          yhs=1;  //已回溯，环上仅回溯这一次
        }
        break;
      }
    }
    for(int y:e[x]){
      if(vis[y]) continue;
      if(inc[y]&&flag) continue; //不访问环点y，从此处回溯
      dfs2(y);
    }
  }
  else{ //x在环外
    for(int y:e[x])if(!vis[y]) dfs2(y);
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1,u,v; i<=m; i++){
    scanf("%d%d",&u,&v);
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end()); //出边排序
  
  if(m==n-1) dfs1(1);
  else{
    find(1,1);
    tmp=0x3f3f3f3f;
    dfs2(1);
  }
  for(int i=1; i<=n; i++) printf("%d ",path[i]);
}