题解 | #回路#

思路：根据题意建图，用邻接表存储。

根据题意可知，是否存在包含三个节点的回路，其中一个节点是1号节点。

思路：
从1号格子开始dfs,深度遍历（一条路走到底），看是否还能回到1号格子。

用vis数组记录当前节点是否被访问过，一个节点只能被访问一次。

需要一个深度变量（depth）记录节点深度。

注意点：要添加判断条件，防止只包含两个节点的回路。
例如：1->2,2->1的回路。

class Solution
{
public:

    string solve(vector<int>& param, vector<Point>& edge)
    {
        int n=param[0],m=param[1];//n个节点，m条边
        vector<vector<int>> graph(n+1);//建图
        vector<int> vis(n+1,0);//vis数组

        for(int i=0;i<m;i++)//建立邻接表
        {
            int x=edge[i].x,y=edge[i].y;
            graph[x].push_back(y);//无向图，双向
            graph[y].push_back(x);
        }
        vis[1]=1;//标记1号节点已访问
        if(dfs(1,vis,graph,0))//令1号节点深度为0
            return "Yes";
        else
            return "No";
    }
    bool dfs(int x,vector<int> &vis,vector<vector<int>> graph,int depth)//查询是否包含1号节点的回路
    {
        int n=graph[x].size();
        for(int i=0;i<n;i++)//遍历从节点x出发，所到达的节点y
        {
            int y=graph[x][i];
            if(y==1&&depth!=1)//如果再次访问到1号节点（1号节点深度为0）并且当前节点深度不为1，则说明该回路不是两个节点构成的回路，即1->2,2->1的回路，则返回true
                return true;
            if(!vis[y])//未被访问的节点可以访问
            {
                vis[y]=1;
                if(dfs(y,vis,graph,depth+1))//深度遍历，并且儿子节点深度+1
                    return true;
                vis[y]=0;
            }
        }
        return false;
    }
};

 时间复杂度：,n是节点数，m是边数，遍历每个节点和每条边。
 空间复杂度： ，n是节点数，最坏情况每两个节点都有边。

思路：

如果一个节点同时有两个不同的标记，则发生冲突，说明有回路。

vis数组不仅记录当前节点是否被访问过，而且还能充当节点的标记值。

class Solution
{
public:

    string solve(vector<int>& param, vector<Point>& edge)
    {
        int n=param[0],m=param[1];//n个节点，m条边
        vector<vector<int>> graph(n+1);//建图
        vector<int> vis(n+1,0);//vis数组

        for(int i=0;i<m;i++)//建立邻接表
        {
            int x=edge[i].x,y=edge[i].y;
            graph[x].push_back(y);//无向图，双向
            graph[y].push_back(x);
        }
        if(bfs(vis,graph))
            return "Yes";
        else
            return "No";
    }
    bool bfs(vector<int> &vis,vector<vector<int>> graph)//查询是否包含1号节点的回路
    {
        int flag=2;
        queue<int> q;
        q.push(1);//1号节点入队列
        vis[1]=1;//标记1号节点已访问（即已入队列），并且标记为1
        while(!q.empty())
        {
            int x=q.front();//出队列
            q.pop();
            int n=graph[x].size();
            for(int i=0;i<n;i++)//遍历x节点所延伸到的节点y
            {
                int y=graph[x][i];
              
                if(vis[y]==0)//未访问的节点可以访问
                {
                    if(x==1)
                        vis[y]=flag++;//如果是1号节点，则给1号节点的第一代儿子节点取不同编号（标记号从2开始），使得vis[y]！=0,也充当了已访问该节点的作用
                    else
                        vis[y]=vis[x];//否则跟随父节点的标记
                    q.push(y);
                }
                else if(vis[x]!=vis[y]&&y!=1)//调到这里说明y节点已访问，再判断如果y节点与x节点编号不一致并且子节点不是1号节点（即排除1->2,2->1的回路），则说明发生冲突，有回路
                {
                    return true;
                }
            }
        }
        return false;
    }
};

 时间复杂度：,n是节点数，m是边数，遍历每个节点和每条边。
 空间复杂度： ，n是节点数，最坏情况每两个节点都有边。