685.冗余连接II

admin2024-05-15  0

685.冗余连接II


题目链接:685.冗余连接II

代码如下:

//并查集
//参考链接:https://leetcode.cn/problems/redundant-connection-ii/solutions/417164/685-rong-yu-lian-jie-iibing-cha-ji-de-ying-yong-xi
class Solution 
{
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) 
    {
        int inDegree[N]={0};
        n=edges.size();
        for(int i=0;i<edges.size();i++)
        {
            inDegree[edges[i][1]]++;//统计入度
        }
        vector<int> vec;//记录入度为2的边
        for(int i=edges.size()-1;i>=0;i--)
        {
            if(inDegree[edges[i][1]]==2)
            {
                vec.push_back(i);
            }
        }
        if(vec.size()>0)
        {
            if(isTreeAfterRemoveEdge(edges,vec[0]))
            {
                return edges[vec[0]];
            }
            else
            {
                return edges[vec[1]];
            }
        }
        return getRemoveEgdge(edges);
    }
private:
    static const int N = 1010;
    vector<int> father=vector<int>(N, 0);
    int n;//边的数量

    //并查集初始化
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
        }
    }

    //并查集寻根
    int find(int u)
    {
       return u==father[u]?u:father[u]=find(father[u]);//路径压缩
    }

    //并查集判定u,v是否是一个根
    bool isSame(int u,int v)
    {
        u=find(u);
        v=find(v);
        return u==v;
    }

    //将v->v这条边加入并查集
    void join(int u,int v)
    {
        u=find(u);
        v=find(v);
        if(u==v)    return;
        father[v]=u;
    }

    //在有向图中找到删除的那条边,使其成为一棵树
    vector<int> getRemoveEgdge(const vector<vector<int>>& edges)
    {   
        init();
        for(int i=0;i<edges.size();i++)
        {
            if(isSame(edges[i][0],edges[i][1]))//构成了有向环,就需要删除
            {
                return edges[i];
            }
            join(edges[i][0],edges[i][1]);
        }
        return {};
    }

    //删除一条边后判断是否是树
    bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges,int deleteEdge)
    {
        init();
        for(int i=0;i<edges.size();i++)
        {
            if(i==deleteEdge)   continue;
            if(isSame(edges[i][0],edges[i][1]))//构成了有向环,一定不是树
            {
                return false;
            }
            join(edges[i][0],edges[i][1]);
        }
        return true;
    }
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!