题目描述
Lambdaland由N个城市组成，任两个城市间都有一条道路相连。
下个月TBL准备参观Lambdaland。他将从城市1开始，以深度优先搜索顺序参观能所有遍历到的城市。 由于TBL是一位十分重要的人物，*盯上了他，并在他出发之前炸毁了M条道路。
现在*雇佣你写一个程序，求出TBL的参观路线。如果有多解，输出字典序最小的。
20%的分数，N≤1000，M≤50000。
50%的分数，N≤30000，M≤800000。
100%的分数，N≤100000，M≤1000000。
每个城市最多被参观一次，每条道路可被炸毁多次。
思路
暴力dfs，用一个并查集实现把访问过的连续的点缩去，对于一条边$(u,i)$，表示$u,i$直接的道路被炸毁。我们每次访问一个节点$u$时，把出边排序，开一个指针表示下一个跑到哪，用dsu跳到当前字典序最小的，没跑过的点，再用lower_bound判断当前点能不能跑，能跑直接dfs后return
code
#include<bits/stdc++.h>
using namespace std;
const int N=;
vector<int>g[N];
int n,m;
int father[N*];
void init(int x){for(int i=;i<=x;i++)father[i]=i;}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
bool vis[N]; inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} inline void dfs(int u)
{
printf("%d\n",u);
vis[u]=;
father[u]=u+;
int next=find();
sort(g[u].begin(),g[u].end());
while(next<=n)
{
if(!vis[next])
{
int tmp=lower_bound(g[u].begin(),g[u].end(),next)-g[u].begin();
if(tmp>=g[u].size()||next!=g[u][tmp])
{dfs(next);return;}
}next=find(next+);
}
} int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
int x=read(),y=read();
g[x].push_back(y);
g[y].push_back(x);
}
init(N);
dfs();
}