回路

思路

号点对边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";
    }
};
全部评论

相关推荐

研一开学九月份速成的Java,项目是苍穹外卖和黑马点评,算法基础不好,八股文较为熟练,想找份小厂日常实习,希望牛友们给点意见,蟹蟹啦
求offer的花生米很聪敏:三个月学了这么多?spring springmvc mybatis springboot jvm juc,还做完了两个项目,还熟悉八股,会点算法。卧槽,我该反思了。我暑假开始的,就做了外卖,spring springmvc boot 那些原理好多都忘了,还在刷 jvm 视频,八股和算法也没开始
点赞 评论 收藏
分享
一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务