嘟嘟嘟
鉴于一些知道的人所知道的，不知道的人所不知道的原因，我来发NOIPday2T1的题解了。
\(O(n ^ 2)\)的做法自然很暴力，枚举断边断环为链就行了。
所以我是来讲\(O(nlogn)\)的做法的。
准确说是排序复杂度，剩下的都是\(O(n)\)的。
大体思想就是通过一遍dfs\(O(n)\)找到该断的边，然后跑一遍树输出答案就行了。
为了方便，我们把在环外并和环上节点直接相连的点称作某个点的子结点。
那么对于环上的结点\(i\)和下一个结点\(nxt[i]\)，肯定是先把小于\(nxt[i]\)的\(i\)的子结点都走完了，然后判断是该走\(nxt[i]\)还是回溯（就是断边）。
回溯的话，就说明前面有一个子结点比\(nxt[i]\)小而且这个点当时又没走。
所以维护一个变量\(tp\)记录这个东西。首先要清楚的一点是如果回溯的话，那么路径上所有没走过的点都得走。然后每一次遍历点\(i\)的出边，对于所有大于\(nxt[i]\)的子结点取min。如果存在这个点，就必须要更新tp。
然后每一次判断一下，如果\(tp < nxt[i]\)，就断边啦。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m;
vector<int> v[maxn];
bool in[maxn];
int st[maxn], top = 0, a[maxn], cnt = 0;
In bool dfs_cir(int now, int _f) //找环
{
st[++top] = now; in[now] = 1;
for(int i = 0, to; i < (int)v[now].size(); ++i)
{
if((to = v[now][i]) == _f) continue;
if(in[to])
{
while(st[top] ^ to) a[++cnt] = st[top--];
a[++cnt] = st[top];
return 1;
}
if(dfs_cir(to, now)) return 1;
}
in[st[top--]] = 0; return 0;
}
In void dfs(int now, int _f)
{
write(now), space;
for(int i = 0, to; i < (int)v[now].size(); ++i) if((to = v[now][i]) ^ _f) dfs(to, now);
}
bool vis[maxn];
int main()
{
n = read(); m = read();
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
for(int i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
if(m == n - 1) {dfs(1, 0); return 0;}
dfs_cir(1, 0);
reverse(a + 1, a + cnt + 1); //以下三条语句是判断开始往环的那一头走
if(a[2] > a[cnt]) reverse(a + 2, a + cnt + 1);
for(int i = 1; i <= cnt; ++i) vis[a[i]] = 1;
a[cnt + 1] = a[1];
for(int i = 1, tp = a[cnt]; i <= cnt; ++i)
{
int Min = INF;
for(int j = 0, to; j < (int)v[a[i]].size(); ++j)
if(!vis[to = v[a[i]][j]] && to > a[i + 1]) Min = min(Min, to);
if(Min ^ INF) tp = Min;
if(tp < a[i + 1] || i == cnt) //断边，直接从vector中删除元素
{
vector<int>::iterator it = lower_bound(v[a[i]].begin(), v[a[i]].end(), a[i + 1]);
v[a[i]].erase(it);
vector<int>::iterator it2 = lower_bound(v[a[i + 1]].begin(), v[a[i + 1]].end(), a[i]);
v[a[i + 1]].erase(it2);
break;
}
}
dfs(1, 0);
return 0;
}