NC585 题解 | #回路#

题意分析

• 给我们一个图，现在需要我们从1号节点开始走，每条路只能走一边，问最后是否可以重新会到1号节点。简单来说，就是这个图上面是否存在一个环，1号节点是这个环上的点。图上的边没有重边。

思路分析

解法一 DFS

• 首先，这个题目说明了给出的边是没有重复的边的。所以，我们可以利用一个dfs的方法从1号节点开始进行遍历。我们发现，对于，从1号节点开始进行遍历的时候，如果1号节点是在某一个环上面，那么遍历的时候就一定可以回到1号节点。重要的方法就是我们如何进行遍历了。在遍历的时候，我们可以标记我们访问过的节点，对于访问过的节点就没有必要进行遍历了。如果在过程中我们遇到了1号节点，那么直接返回Yes即可。

• 代码如下

  • 可能需要遍历n个节点，并且每个节点最多被遍历一遍，所以时间复杂的为$O\left(n\right)O(n)$O(n)
  • 在遍历的过程中，需要我们标记每个节点被访问的情况，空间复杂度为$O\left(n\right)O(n)$O(n)

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 能回到1号点返回 Yes，否则返回 No
     * @param param int整型vector param[0] 为 n，param[1] 为 m
     * @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
     * @return string字符串
     */
    vector<int> v[100010];
    bool vis[100010];
    bool flag=false; // 用来标记是否找到一条回路
    // 进行dfs递归到每个节点的子节点进行判断
    void dfs(int x,int fa){
        if(flag) return; // 如果已经找到了返回1的路径，那么就没有必要继续往下进行查找了
        vis[x]=true;
        // 寻找子节点
        for(auto y:v[x]){
            if(y==fa) continue;
            if(y==1){ // 如果找到了，那么直接返回
                flag=true;
                return;
            }
            // 如果这个结点已经被走过，那么就不能继续走了，因为题目中要求只能走一遍
            if(vis[y]) continue;
            dfs(y,x);
        }
    }
    string solve(vector<int>& param, vector<Point>& edge) {
        // write code here
        // 先存储路径的信息
        for(auto a:edge){
            v[a.x].push_back(a.y);
            v[a.y].push_back(a.x);
        }
        dfs(1,0);
        return flag?"Yes":"No";
    }
};

解法二 BFS

• 很多时候，可以用DFS进行解答的，也可以使用BFS进行解答。所以，我们来想一下BFS如何进行求解。

• 其实BFS就是一个利用队列来进行优化的一种方法。也可以称做广度优先遍历。就是我们把这棵树分为若干层，一层一层进行遍历。但是我们会发现一个问题，就是我们如果采用的是层序遍历的话就很难对边是否访问进行标记。我们再来回顾一下我们是如何进行DFS的，我们是对某一条路径递归到底，这样如果我们存在一个合法的环路的话，那么就一定可以递归回到1号结点。但是层序遍历不是对某一条路径递归到底，这该怎么办呢？

• 我们结合下面的图进行解释。

• 我们既然是按照一层一层进行遍历的，那么就可以将每条路径分为多干个主分支的，我们先对1号结点的儿子进行标记，分为不同的分支，然后我们继续进行BFS，记录每个结点属于哪一个分支的，如果某一个结点同时属于多个不同的主分***么说明形成了一个包含1的环。

• 代码如下

  • 可能需要对每个结点进行遍历，时间复杂度为$O\left(n\right)O(n)$O(n)
  • 需要开数组存储n个结点的相关的信息，即所在的主分支编号，空间复杂度为$O\left(n\right)O(n)$O(n)

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 能回到1号点返回 Yes，否则返回 No
     * @param param int整型vector param[0] 为 n，param[1] 为 m
     * @param edge Point类vector Point.x , Point.y 分别为一条边的两个点
     * @return string字符串
     */
    vector<int> v[100010];
    int fa[100010];
    string solve(vector<int>& param, vector<Point>& edge) {
        // write code here
        memset(fa,-1,sizeof(fa));
        for(auto a:edge){
            v[a.x].push_back(a.y);
            v[a.y].push_back(a.x);
        }
        
        
        
        queue<int> q;
        int cnt=0; // 用来标记1号节点的分支数目
        // 先对1号节点的每个分支进行标记编号
        for(auto x:v[1]){
            fa[x]=++cnt;
            q.push(x);
        }
        
        while(!q.empty()){
            int now=q.front();
            q.pop();
            
            // 对当前节点的子节点进行遍历
            for(auto x:v[now]){
                // 这里要特判1的子节点的情况
                if(x==1) continue;
                // 如果当前这个节点之前就属于某一条分支，后面又属于另一条分***么说明成环了
                if(fa[x]!=-1){
                    if(fa[x]!=fa[now]){
                        return "Yes";
                    }
                }
                // 更新这个节点的所在的分支
                fa[x]=fa[now];
                q.push(x);
            }
        }
        
        return "No";
    }
};