网站建设 国外,深圳展台制作公司,html5手机网站模板下载,用wordpress做网站leetcode-1971:寻找图中是否存在路径
并查集可以解决的问题是#xff1a;判断两个点是否在同一个集合之中
并查集模版#xff1a;
最重要的两部#xff1a;将两点连接以及对某一节点寻根。
一、初始化#xff1a;{init()}
将每个节点的父节点初始化为自身。
二、寻根…leetcode-1971:寻找图中是否存在路径
并查集可以解决的问题是判断两个点是否在同一个集合之中
并查集模版
最重要的两部将两点连接以及对某一节点寻根。
一、初始化{init()}
将每个节点的父节点初始化为自身。
二、寻根{find(int x)}
这里我们采用递归的方法首先我们需要判断当前节点是否为一个集合的根节点x father[x],如果是根节点那么寻根的结果就是自身x如果不是那么需要递归地寻找当前节点的父节点的根节点也就是find(father[x])这里我们采用一个三目运算符简化写法return x father[x] ? x : find(father[x])
这里我们会发现寻根的过程会非常复杂 这里我们发现当我们对一个节点进行寻根的过程中时如果该节点的度数很大那么就需要递归多次所以我们可以将上图转化为下图的形式 我们只需要在find函数的最后返回结果将当前节点的父节点设置为根节点即可
return x father[x] ? x : father[x] find(father[x]); 三、构建连接图{join(int u, int v)}
首先判断当前传入的两点是否存在同根现象首先进行寻根如果两点的根是同一个节点那么这两点属于同一集合无需相连如果两点的根不同说明不在同一个集合之中就将两点相连father[v] u;
在这里我们需要注意父节点的指向问题因为我们发现find函数内部的代码与issame函数的代码存在部分类似的问题所以我们可以实践代入一下
如果我们讲join的类似部分进行替换
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u find(u);v find(v);return u v;
}// 将v-u 这条边加入并查集
void join(int u, int v) {if (isSame) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v] u;
}
我们用一个例子2 - 1, 3 - 2.最终3应该指向1但是我们带入上面代码
join(1, 2):1 2的父节点是自身所以father[2] 1.
join(2,3):两者的根节点依旧不同所以相连father[3] 2.
到这里我们就会发现问题这种写法是将有相图转变成了无相图这使得只是讲两个节点相连并不能够判断两节点的根节点是否为相同的。
所以正确的写法还是找到传入的两节点的根节点并对根节点进行判断是否相连接。
void join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v] u;
}
代码
class Solution { public: int n 2e6; vectorint father; vectorint rank; void init(){ father.resize(n); rank.resize(n, 1); for(int i 0; i n; i){ father[i] i; } } int find(int x){ return x father[x] ? x : father[x] find(father[x]); } void join(int u, int v){ u find(u); v find(v); if(u v){ return; }else { if(rank[u] rank[v]){ father[u] v; }else{ father[v] u; } if(rank[u] rank[v] u ! v) rank[v]; } } bool issame(int u, int v){ if(find(u) find(v)) return true; else return false; } bool validPath(int n, vectorvectorint edges, int source, int destination) { init(); int c edges.size(); for(int i 0; i c; i){ int x edges[i][0]; int y edges[i][1]; join(x, y); } if(issame(source, destination)) return true; else return false; } }; leetcode - 2236:统计无相图中无法相互到达的点对数
这道题我们的思路是统计所有联通集合中点的数目对于单独的未联通的节点我们可以在判断的时候将其size置为0再处理。
1这道题由于当数据过大时递归规模太大会导致溢出的问题为了节省空间我们就直接在初始化的步骤上进行传参操作将问题规模大小n传入后并改变三个数组的规模。
2在压缩路径的过程中将度数小的树加入到度数大的树时我们只需要使得合成后的度数尽量地小不需要再对度数小的树度数进行修改这里会有一个问题就是在哪里对rank度数进行增加或减少呢因为一开始都是初值1这里我们就是在一开始添加两个节点的时候两个节点必然都是度数为1所以我们只需要在两者度数相等时也就是建树的最初过程中对rank进行加1操作。
3我们要注意最后我们求的res是双向的也就是会遍历两遍所以我们需要对结果除以二才能的最后结果。 class Solution { public: vectorint father; vectorint rank; vectorint size; void init(int n){ father vectorint(n, 0); rank vectorint(n, 1); size vectorint(n, 1); for(int i 0; i n; i){ father[i] i; } } int find(int x){ return x father[x] ? x : father[x] find(father[x]); } void join(int u, int v){ u find(u); v find(v); if(u v){ return; }else{ if(rank[u] rank[v]){ father[v] u; size[u] size[v]; }else{ father[u] v; size[v] size[u]; } if(rank[u] rank[v] u ! v){ rank[u] 1; } } } long long countPairs(int n, vectorvectorint edges) { init(n); for(int i 0; i edges.size(); i){ join(edges[i][0], edges[i][1]); } long long res 0; for(int i 0; i n; i){ res n - size[find(i)]; } return res / 2; } };
leetcode -1319:连通网络的操作次数
我们需要求的所给网络图中的连通分量的个数n 再求将独立分量连接到连通分量所需要的操作数。
1我们需要明确的一点是join操作中当我们所要链接的两个点同根时会直接返回并不会进行下面的操作从而对联通分量的数目进行-1操作这也是的我们最后求出的setcount数量就是图中联通分量的个数将这些所有的联通分量连接起来组成一个全连通分量就是最后的我们的结果也就是setcount - 1. class Solution { public: vectorint father; vectorint rank; void init(int n){ father vectorint(n, 0); rank vectorint(n, 1); for(int i 0; i n; i){ father[i] i; } } int find(int x){ return x father[x] ? x : father[x] find(father[x]); } void join(int u, int v, int res){ u find(u); v find(v); if(u v){ return; } if(rank[u] rank[v]){ father[v] u; }else{ father[u] v; } if(rank[u] rank[v] u ! v){ rank[u] 1; } res--; } int makeConnected(int n, vectorvectorint connections) { if(connections.size() n - 1){ return -1; } int res n; init(n); for(int i 0; i connections.size(); i){ join(connections[i][0], connections[i][1], res); } return res - 1; } };
