回路

思路

从 号点对边dfs，判断 号点是否在一个环中即可。
时间复杂度：

code

class Solution {
#define maxn 100010
private:
    int n, m, L;
    vector<int> g[maxn];
    bool vis[maxn];
    bool fg = false;
public:
    void dfs(int x, int fa = 0) {
        if (fg) return;
        if (fa && x == 1) return fg=1,void();
        if (vis[x]) return;
        vis[x] = 1;
        for (auto v: g[x]) {
            if (v == fa) continue;
            dfs(v, x);
        }
    }

    string solve(vector<int>& param, vector<Point>& edge) {
        n = param[0], m = param[1];
        for (int u, v, i = 0; i < m; ++i) {
            u = edge[i].x;
            v = edge[i].y;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1);
        string res;
        if (fg) res = "Yes";
        else res = "No";
        return res;
    }
};

优化解法

并查集的思路是找所有的联通块如果将要放进集合的两个点有共同的父亲，则说明环，然后在环上找 。

Code

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

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字符串
     */
    int find_(int x,vector<int>& parent){return parent[x]==-1?x:find_(parent[x],parent);}
    bool union_(int x,int y,vector<int>& parent,vector<int>& rank)
    {
        int x_r=find_(x,parent),y_r=find_(y,parent);
        if(x_r==y_r) return true;
        if(rank[x_r]<rank[y_r])
            parent[x_r]=y_r;
        else if(rank[x_r]>rank[y_r])
            parent[y_r]=x_r;
        else
        {
            rank[x_r]++;
            parent[y_r]=x_r;
        }
        return false;
    }
    string solve(vector<int>& param, vector<Point>& edge) {
        // write code here
        vector<int>parent(param[0]+1,-1),rank(param[0]+1);
        for(auto& it:edge)
            if(union_(it.x,it.y,parent,rank))
                for(int i=it.x,j=it.y;i!=-1||j!=-1;)
                {
                    if(i==1||j==1) return "Yes";
                    i=i==-1?-1:parent[i],j=j==-1?-1:parent[j];
                }
        return "No";
    }
};