题目的主要信息：

n个节点，m条边，数组edge记录的是有边的两个节点
判断这个图是否有从1号节点开始的回路

方法一：dfs

具体做法：

首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如果没有则继续深度优先搜索往下走，如果最后也没有回到节点1，返回false。

class Solution {
public:
    bool dfs(int cur, int pre, vector<vector<int>>& G, vector<int>& vis){
        for(int i = 0; i < G[cur].size(); i++){ //遍历每个节点
            int next = G[cur][i];
            if(next == pre) //不能是前序节点
                continue;
            if(!vis[next]){
                vis[next] = true;
                if(next == 1 || dfs(next, cur, G, vis)) //回到了1或者子节点的dfs回到了1
                    return true;
            }
        }
        return false;
    }
    string solve(vector<int>& param, vector<Point>& edge) {
        int n = param[0];
        int m = param[1]; //先找到m和n
        vector<vector<int> > G(n + 1);
        vector<int> vis(n + 1, 0);  //记录是否访问过
        for(int i = 0; i < m; i++){ //构建图
            G[edge[i].x].push_back(edge[i].y);
            G[edge[i].y].push_back(edge[i].x);
        }
        if(dfs(1, -1, G, vis)) //深度优先搜索判断
            return "Yes";
        return "No";
    }
};

复杂度分析：

时间复杂度： $O (m + n)$ ，构建图遍历 $m$ ，深度优先搜索遍历 $n$ 个节点
空间复杂度： $O (n^{2})$ ，最坏情况下保存图的列表G为邻接矩阵

方法二：bfs

具体做法：

同理，有dfs就会有bfs。我们可以广度优先搜索与节点1相连的所有结点，并对其每个做一个单独的标记，然后继续广度优先搜索，子节点的的标记就等于父节点的标记（只有节点1相连的不一样），如果广度优先搜索到后面，遇到相邻两个不相同标记的节点，说明这里可以构成一圈即一个回路。如下图所示：图片说明

class Solution {
public:
    string solve(vector<int>& param, vector<Point>& edge) {
        int n = param[0];
        int m = param[1]; //先找到m和n
        vector<vector<int> > G(n + 1);
        vector<int> vis(n + 1, -1);  //记录是否访问过
        for(int i = 0; i < m; i++){ //构建图
            G[edge[i].x].push_back(edge[i].y);
            G[edge[i].y].push_back(edge[i].x);
        }
        queue<int> q; //bfs辅助队列
        q.push(1);
        vis[1] = 0; //从1号开始访问
        while(!q.empty()){ //bfs
            int cur = q.front();
            q.pop();
            for(int i = 0; i < G[cur].size(); i++){
                int next = G[cur][i];
                if(vis[next] == -1){ //未访问过
                    q.push(next); //进入队列后续访问
                    if(cur == 1)  //标记
                        vis[next] = i + 1;
                    else
                        vis[next] = vis[cur];
                }else{
                    if(vis[next] != vis[cur] && next != 1) //不同点相遇，有回路
                        return "Yes";
                }
            }
        }
        return "No";
    }
};

复杂度分析：

时间复杂度： $O (m + n)$ ，构建图遍历 $m$ ，深度优先搜索遍历 $n$ 个节点
空间复杂度： $O (n^{2})$ ，最坏情况下保存图的列表G为邻接矩阵

题解 | #回路#

题目的主要信息：

方法一：dfs

方法二：bfs