题意概述

  • n个结点，m条边，边所连接的两个结点之间可相互到达（无向边），且一条边只可走一次
  • 若有从1号结点开始的回路则返回true，否则返回false

相关知识

  • 图的深度优先搜索模板（邻接表实现）
    const int MAXV=1000;
const int inf=0x3fffffff;
int n;
vector<vector<int> >e;//或者vector<int>e[MAXV]; 
bool vis[MAXV];
void DFS(int u,int depth){//u为当前访问顶点标号，depth为深度 
  vis[u]=true;//置u已被访问 
  for(int i=0;i<e[u].size();i++){//枚举u所能到达的每个分支顶点 
      int v=e[u][i];
      if(vis[v]==false)DFS(v,depth+1);//如果v未访问，且u可达v，访问v深度+1    
  }
}
void DFSTrave(){//遍历图 
  for(int u=0;u<n;u++){//对每个顶点u 
      if(vis[u]==false)DFS(u,1);//如果u未访问，访问它所在的联通块，1表示初始为第一层 
  }
}
  • 图的广度优先搜索模板（邻接表实现）
    const int MAXV=1000;
const int inf=0x3fffffff;
int n;
vector<int>e[MAXV]; 
bool vis[MAXV];
void BFS(int u){
  queue<int>q;//定义队列q，并让起点入队 
  q.push(u);
  vis[u]=true;
  while(!q.empty()){//在队列非空时，不断取队首元素访问 
      int u=q.front();
      q.pop();
      for(int i=0;i<e[u].size();i++){//让队首元素能到达结点入队 
          int v=e[u][i];
          if(vis[v]==false){
              q.push(v);
              vis[v]=true;
          }
      }
  }
}
void BFSTrave(){//遍历图
  for(int u=0;u<n;u++){//对每个顶点u
      if(vis[u]==false)BFS(u);//如果u未访问，访问它所在的联通块
  }
}

    方法一：DFS

    思路与具体做法

  • 用邻接表存储图，然后从1号结点开始深度优先搜索遍历连通图，并对访问过的点用vis数组进行标记，直到遍历完所有点；
  • 递归起点1号结点设深度为1，若某点的后继结点为1且当前递归深度不为2，即为存在从1号结点开始的回路。 
class Solution {
public:
    int ans=0;//是否有回路 
    bool DFS(int u,int depth,vector<bool>&vis,vector<vector<int> >&e){
        vis[u]=true;//标记当前点u已访问 
        for(int i=0;i<e[u].size();i++){//遍历u所能到达的所有点 
            int v=e[u][i];//u的后继点 
            if(v==1&&depth!=1)return ++ans;//最终能回到点1 
            if(vis[v]==false)DFS(v,depth+1,vis,e);//u的后继点未访问，则访问它    
        }
        return ans;
    } 
    string solve(vector<int>& param, vector<Point>& edge) {
        int n=param[0],m=param[1];//n个结点，m条边
        vector<bool>vis(n+1,false);//判断各点有没有访问过
        vector<vector<int> >e(n+1);//邻接表存图 
        for(int i=0;i<m;i++){//读入边 
            int x=edge[i].x,y=edge[i].y;
            e[x].push_back(y);
            e[y].push_back(x);
        } 
        if(DFS(1,0,vis,e))return "Yes";
        else return "No";
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，m为边数，n为结点数，初始建图遍历长度为m的边集，递归中搜索了n个结点
空间复杂度：，n为结点数，最坏情况任意两点间有边，此时图最大

方法二：BFS

思路与具体做法

  • 广度优先搜索遍历连通图，对搜索起点的所有孩子结点标记上不同“路标”，搜索到其他结点时均继承父结点的“路标”，同时对访问过的点进行标记；这里可用vis数组同时进行是否访问过标记与加入路标，具体做法为对访问过点，加入对应路标；
  • 如果存在一个访问过的结点，有两个冲突的“路标”，即该点属于两条从根结点延伸出来的路径，即可证，有环路；
    图片说明 
class Solution {
public:
    bool BFS(int u,vector<int>&vis,vector<vector<int> >&e){
        queue<int>q;//定义队列q，并让起点入队 
        q.push(u);
        vis[u]=true; 
        int id=1; 
        while(!q.empty()){//在队列非空时，不断取队首元素访问 
            int u=q.front();
            q.pop();
            for(int i=0;i<e[u].size();i++){//让队首元素能到达结点入队 
                int v=e[u][i];//u的后继点             
                if(vis[v]==false){//后继点未访问则访问它 
                    q.push(v);
                    if(u==1)vis[v]=id++;//从根结点开始进行分叉标记 
                    else vis[v]=vis[u];//除根结点的子结点外的其他子结点继承父结点的路标 
                }else if(vis[v]!=vis[u]){//访问过，且该点属于两条从根结点延伸出来的路径，即可证，有环路 
                    return true;
                }
            }
        }
        return false;
    }
    string solve(vector<int>& param, vector<Point>& edge) {
        int n=param[0],m=param[1];//n个结点，m条边
        vector<int>vis(n+1,0);//判断各点有没有访问过
        vector<vector<int> >e(n+1);//邻接表存图 
        for(int i=0;i<m;i++){//读入边 
            int x=edge[i].x,y=edge[i].y;
            e[x].push_back(y);
            e[y].push_back(x);
        } 
        if(BFS(1,vis,e))return "Yes";
        else return "No";        
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，m为边数，n为结点数，初始建图遍历长度为m的边集，BFS中搜索了n个结点
空间复杂度：，n为结点数，最坏情况任意两点间有边，此时图最大