[NOIp2018提高组]旅行：

题目大意：

一个\(n(n\le5000)\)个点，\(m(m\le n)\)条边的连通图。可以从任意一个点出发，前往任意一个相邻的未访问的结点，或沿着第一次来这个点的边返回。需要遍历每一个点。没经过一个新的结点，就将这个结点写下来。最终可以得到一个序列。求字典序最小的序列。

思路：

对于树的情况，显然从\(1\)出发，每次从字典序最小的相邻结点DFS即可。

对于有环的情况，由于环只有一个，我们可以将环找出来，枚举删掉环上的每一条边，然后按树的情况求解即可。

时间复杂度\(\mathcal O(n^2)\)。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}const int N=5001;struct Edge { int u,v;};Edge edge[N];std::vector
           
            
              > g[N];bool vis[N],mark[N];std::stack
             
              
                > stk;void dfs(const int &x,const int &par) { vis[x]=true; for(unsigned i=0;i

e[N];inline void add_edge(const int &u,const int &v) { e[u].insert(v); e[v].insert(u);}inline void del_edge(const int &u,const int &v) { e[u].erase(v); e[v].erase(u);}int s[N],ans[N];void solve(const int &x,const int &par) { s[++s[0]]=x; for(std::set

::iterator i=e[x].begin();i!=e[x].end();i++) { const int &y=*i; if(y==par) continue; solve(y,x); }}inline bool check(int a[],int b[],const int &n) { for(register int i=1;i<=n;i++) { if(a[i]

b[i]) return false; } return false;}int main() { const int n=getint(),m=getint(); for(register int i=0;i

转载于:https://www.cnblogs.com/skylee03/p/9961821.html

你可能感兴趣的文章