并查集
参考《算法笔记》
三要素：并，查，集。
并差集与一个算法有关，kruskal算法，就可通过并查集实现。
1.并：合并，合并两个集合。
2.查找：判断两个元素是否在一个集合。
int father[N];//并查集可以通过数组实现。
father[i]表示元素i的父节点，father[1]=2,表示元素1的父节点是元素2，如果father[i] = i，则说明元素i是该集合的根节点，对于同一个集合来说，只存在一个根节点，且将其作为所属集合的标识。
1.初始化，每个元素是独立集合。
for(int i=1;i<=N;i++){
father[i]=i;
}
2.查找，对给定的节点寻找根节点的过程，反复寻找父节点。
int findFather(int x){
while(x!=father[x]){//如果不是根节点，继续循环
x=father[x];
}
return x;
}
int findFather(int x){
if(x==father[x]) return x;
else return findFather(father[x]);
}
3.合并
合并是指把两个集合合并成一个集合。
1）.对于 a,b ,首先判断它们是否属于同一集合。可以调用查找函数，查找根节点，判断其根节点是否相同。
2）.合并两个集合。获得a的根节点faA和b的根节点faB，令father[faA]=faB即可，或者令father[faB]=faA。
注意一定要找到根节点后再设指向。
void Union(int a,int b){
int faA=findFather(a);
int faB=findFather(b);
if(faA!=faB){
father[faA]=faB;
}
}
找最小生成树的思想：
kruskal算法
1.把边从小到大排序。eloge
2.从小到大遍历边顶点A,B，如果A,B父节点不同，合并这个集合，如果相同，跳过这条边。
3.如此循环加到生成树中的边集数量为n-1时停止。最后得到的边集合是最小生成树。
合适的数据结构可以达到O（E*lgV）
lc684
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个题可以用dfs/bfs/并查集，就是一个查找图中有没有环的题。
执行用时：4 ms, 在所有 C++ 提交中击败了97.88%的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了93.37%的用户
class Solution {
public:
int findFather(int arr[],int x){
int index=x;
while(arr[index]!=index)
index=arr[index];
return index;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
//dfs/bfs/并查集
int ers[edges.size()+1];
for(int i=0;i<edges.size()+1;i++){
ers[i]=i;
}
vector<int>res;
for(int i=0;i<edges.size();i++){
int a=edges[i][0];
int b=edges[i][1];
int fa=findFather(ers,a);
int fb=findFather(ers,b);
if(fa!=fb)
ers[fa]=fb;
else{
res.push_back(a);
res.push_back(b);
return res;
}
}
return res;
}
};
lc685 冗余连接2
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
难点应该在于想清楚所有的情况。分解成小问题挨个解决即可。
1、入度=2，肯定要删除的。1) 有环，删入度=2且在环中那条边。2）无环，默认删后一个。
2、入度没有等于2的，那么肯定在环中，删环里最后一个发现的边即可，直接用并查集。
class Solution {
public:
//并查集
int findFather(int arr[][3],int x){
int index=x;
while(arr[index][2]!=index)
index=arr[index][2];
return index;
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int ers[edges.size()+1][3];
for(int i=0;i<edges.size()+1;i++){
ers[i][0]=0;
ers[i][1]=i;
ers[i][2]=i;
}
vector<int>res;
for(int i=0;i<edges.size();i++){
int a=edges[i][0];
int b=edges[i][1];
ers[b][0]+=1;//入度
if(ers[b][1]==b){
ers[b][1]=a;
}else{
ers[b][2]=a;
}
}
for(int i=0;i<edges.size()+1;i++){
if(ers[i][0]==2){
int index=ers[i][1];
while(ers[index][1]!=i&&ers[index][1]!=index){
index=ers[index][1];//有环且环是1
}
if(ers[index][1]==i){
res.push_back(ers[i][1]);
res.push_back(i);
cout<<ers[i][1]<<endl;
cout<<i<<endl;
return res;
}
cout<<"ers"<<endl;
res.push_back(ers[i][2]);
res.push_back(i);
return res;
}
}
// cout<<"[[]]"<<endl;
for(int l=0;l<edges.size();l++){
ers[l][2]=l;
}
for(int i=0;i<edges.size();i++){
int a=edges[i][0];
int b=edges[i][1];
int fa=findFather(ers,a);
int fb=findFather(ers,b);
if(fa!=fb)
ers[fb][2]=fa;
else{
// cout<<a<<b<<endl;
res.push_back(a);
res.push_back(b);
}
}
return res;
}
};
网友评论