685.冗余连接
4:03
// 定义并查集类
class UnionFind{// 构造函数初始化并查集constructor(n){this.parent = new Array(n).fill(0).map((item,index)=>index)this.rank = new Array(n).fill(1)this.count = n}// 查找元素的根节点find(x){if(this.parent[x] !== x){this.parent[x] = this.find(this.parent[x])}return this.parent[x]}// 合并两个集合union(x,y){let rootX = this.find(x)let rootY = this.find(y)if(rootX === rootY){return false}if(this.rank[rootX] < this.rank[rootY]){this.parent[rootX] = rootYthis.rank[rootY] += this.rank[rootX]}else{this.parent[rootY] = rootXthis.rank[rootX] += this.rank[rootY]}this.count--}// 判断两个元素是否属于同一个集合connected(x,y){return this.find(x) === this.find(y)}// 获取集合的数量getCount(){return this.count}
}
/*** @param {number[][]} edges* @return {number[]}*/
// 考虑三种情况：
// 1.附加边指向了我们的根结点，导致所有的节点都有一个父节点，导致出现环；
// 2.附加边没有指向我们根节点，会出现树中某个节点会有两个父亲节点；也有可能会出现环路；
var findRedundantDirectedConnection = function(edges) {// 先要获取节点的个数，就是边的个数let nodeCount = edges.length// 根据节点的个数构造并查集，长度加1，避免从0开始let uf = new UnionFind(nodeCount + 1)//怎么记录产生了两个父节点let parent=[] //记录每一个节点的父节点是多少for(let i=1;i<(nodeCount+1);i++){//边的长度+1parent[i] = i//初始化}let conflit = -1 //记录产生两个父节点的边let cycle = -1 //记录产生环路的边for(i in edges){let edge=edges[i];let node1=edge[0],node2=edge[1];//拿到了两个节点if(parent[node2] != node2){//node2这个节点有两个父节点conflit = i;//记录产生两个父节点的边}else{//否则没有双重父节点，就把他们连起来parent[node2] = node1;if(uf.find(node1) == uf.find(node2)){//如果两个节点的根节点相同，说明产生了环路cycle = i;//记录产生环路的边}else{//既有环路，又有双重节点uf.union(node1,node2);//把两个节点连起来}}}if(conflit < 0){//没有双重父节点产生，就把环路记录下来return edges[cycle];//返回产生环路的边}else{//只有双重父节点产生let conflitEdge = edges[conflit];//拿到产生双重父节点的边if(cycle >= 0){//既有环路，又有双重节点return [parent[conflitEdge[1]],conflitEdge[1]];//有两个入度点}else{return conflitEdge;//只有一个入度点}}
};