做旅行社网站多少钱,二维码生成软件,o2o网站建设策划,中职网站建设与管理专业题目#xff1a;684. 冗余连接
思路
并查集#xff1b; 从前往后遍历#xff0c;如果不属于同一个集合#xff08;不是同一个爸爸#xff09;#xff0c;就加入#xff0c;否则就返回这条边#xff1b; 因为不属于同一个集合#xff0c;加入可以形成树#xff0c;要…题目684. 冗余连接
思路
并查集 从前往后遍历如果不属于同一个集合不是同一个爸爸就加入否则就返回这条边 因为不属于同一个集合加入可以形成树要不然会成环而且题目限定整个图是一棵树加一条边所以多出来的那个删掉之后就刚好形成一棵树就是这么巧
代码
// 删除之后都拥有同一个爸爸
class Solution {
private:int n 1005;int father[1005] {0};void init(){int i;for(i 0; i n; i){father[i] i;}}int find(int u){if(u father[u]){return u;}else{return father[u] find(father[u]);}}bool isSame(int u, int v){u find(u);v find(v);if(u v){return true;}return false;}// u - vvoid join(int u, int v){u find(u);v find(v);if(u v){return;}father[u] v;}public:vectorint findRedundantConnection(vectorvectorint edges) {int i, u, v;init();for(i 0; i edges.size(); i){u edges[i][0];v edges[i][1];if(!isSame(u, v)){join(u, v);}else{return edges[i];}}return {};}
};
