参观路线——并查集+dfs

题目描述

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();

}