**********************************ALGO UNION FIND -*********************
//(N)LOG(N)
#include<bits/stdc++.h>
using namespace std;
int rankx[10000],parent[100000];
vector<pair<int,int> > graph[10000];
int findx(int x)
{
if(parent[x]==x)
return x;
else
return findx(parent[x]);
}
void Union(int x,int y)//UNION BY RANK(PATH COMPRESSION)
{
int p1,p2;
p1=findx(x);
p2=findx(y);
if(rankx[p1]>rankx[p2])
{
parent[p2]=p1;
}
else
{
parent[p1]=p2;
// only when rank of bote r same than rank of one is increased....
if(rankx[p1]==rankx[p2])
{
rankx[p2]++;
}
}
}
int main()
{
int n,m,i,x,y,w;
cin>>n>>m;
set<pair<int,pair<int,int > > > s;
set<pair<int,pair<int,int > > > :: iterator it;
for(i=0;i<m;i++)
{
cin>>x>>y>>w;
graph[x].push_back({y,w});
graph[y].push_back({x,w});
s.insert({w,{x,y}});
}
for(i=0;i<=n;i++)
parent[i]=i;
while(!s.empty())
{
it=s.begin();
pair<int,pair<int,int> > p=*it;
s.erase(it);
x=p.second.first;
y=p.second.second;
if(findx(x)!=findx(y))
{
Union(x,y);
cout<<x<<" "<<y<<endl;
}
}
return 0;`
}
**********************************easier************************************nlog(n)
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int rank[100010];
int parent[100010];
int find(int node)
{
if(parent[node]==node)
{
return node;
}
else
find(parent[node]);
}
int merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int n;
cin>>n;
int m;
cin>>m;
vector<pair<pair<int ,int >,int> > v;
int a , b,c;
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
v.push_back(make_pair(make_pair(c,a),b) );
}
for(int i=1;i<=n;i++)
{
parent[i]=i;
}
sort(v.begin(),v.end());
long long int cost=0;
for(int i=0;i<m;i++)
{
a=v[i].first.second;
b=v[i].second;
if(find(a)!=find(b))
{
merge(a,b);
cost+=v[i].first.first;
}
}
cout<<cost<<endl;
return 0;
}
/****************************** for path compression ****************************
for path compression we need to improve find operation .. using path compression we set all nodes in same set having same parent so that deciding which element is in which set wiil be done in very less time
some time in o(1);;
lli find(lli a)
{
if(par[a]!=par[par[a]])
{
par[a]=find(par[a]);
}
return par[a];
/**************************************end**********************************
**************************************practice questions ****************************
Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)
In the previous post, we introduced union find algorithm and used it to detect cycle in a graph. We used followingunion() and find() operations for subsets.
// Naive implementation of findint find(int parent[], int i){ if (parent[i] == -1) return i; return find(parent, parent[i]);} // Naive implementation of union()void Union(int parent[], int x, int y){ int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset;} |
The above union() and find() are naive and the worst case time complexity is linear. The trees created to represent subsets can be skewed and can become like a linked list. Following is an example worst case scenario.
Let there be 4 elements 0, 1, 2, 3
Initially all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
2 3
/
1
/
0
Do Union(2, 3)
3
/
2
/
1
/
0
The above operations can be optimized to O(Log n) in worst case. The idea is to always attach smaller depth tree under the root of the deeper tree. This technique is called union by rank. The term rank is preferred instead of height because if path compression technique (we have discussed it below) is used, then rank is not always equal to height. Also, size (in place of height) of trees can also be used as rank. Using size as rank also yields worst case time complexity as O(Logn) (See this for prrof)
Let us see the above example with union by rank
Initially all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
1 3
/ \
0 2
Do Union(2, 3)
1
/ | \
0 2 3
The second optimization to naive method is Path Compression. The idea is to flatten the tree when find() is called. When find() is called for an element x, root of the tree is returned. The find() operation traverses up from x to find root. The idea of path compression is to make the found root as parent of x so that we don’t have to traverse all intermediate nodes again. If x is root of a subtree, then path (to root) from all nodes under x also compresses.
Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
9
/ | \
4 5 6
/ \ / \
0 3 7 8
/ \
1 2
When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as child of 9 so
that when find() is called next time for 1, 2 or 3, the path to root is
reduced.
9
/ / \ \
4 5 6 3
/ / \ / \
0 7 8 1 2
The two techniques complement each other. The time complexity of each operations becomes even smaller than O(Logn). In fact, amortized time complexity effectively becomes small constant.
Following is union by rank and path compression based implementation to find cycle in a graph.
/***********************************************ALGO END *-*****************************************************************/
//(N)LOG(N)
#include<bits/stdc++.h>
using namespace std;
int rankx[10000],parent[100000];
vector<pair<int,int> > graph[10000];
int findx(int x)
{
if(parent[x]==x)
return x;
else
return findx(parent[x]);
}
void Union(int x,int y)//UNION BY RANK(PATH COMPRESSION)
{
int p1,p2;
p1=findx(x);
p2=findx(y);
if(rankx[p1]>rankx[p2])
{
parent[p2]=p1;
}
else
{
parent[p1]=p2;
// only when rank of bote r same than rank of one is increased....
if(rankx[p1]==rankx[p2])
{
rankx[p2]++;
}
}
}
int main()
{
int n,m,i,x,y,w;
cin>>n>>m;
set<pair<int,pair<int,int > > > s;
set<pair<int,pair<int,int > > > :: iterator it;
for(i=0;i<m;i++)
{
cin>>x>>y>>w;
graph[x].push_back({y,w});
graph[y].push_back({x,w});
s.insert({w,{x,y}});
}
for(i=0;i<=n;i++)
parent[i]=i;
while(!s.empty())
{
it=s.begin();
pair<int,pair<int,int> > p=*it;
s.erase(it);
x=p.second.first;
y=p.second.second;
if(findx(x)!=findx(y))
{
Union(x,y);
cout<<x<<" "<<y<<endl;
}
}
return 0;`
}
**********************************easier************************************nlog(n)
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int rank[100010];
int parent[100010];
int find(int node)
{
if(parent[node]==node)
{
return node;
}
else
find(parent[node]);
}
int merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int n;
cin>>n;
int m;
cin>>m;
vector<pair<pair<int ,int >,int> > v;
int a , b,c;
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
v.push_back(make_pair(make_pair(c,a),b) );
}
for(int i=1;i<=n;i++)
{
parent[i]=i;
}
sort(v.begin(),v.end());
long long int cost=0;
for(int i=0;i<m;i++)
{
a=v[i].first.second;
b=v[i].second;
if(find(a)!=find(b))
{
merge(a,b);
cost+=v[i].first.first;
}
}
cout<<cost<<endl;
return 0;
}
/****************************** for path compression ****************************
for path compression we need to improve find operation .. using path compression we set all nodes in same set having same parent so that deciding which element is in which set wiil be done in very less time
some time in o(1);;
lli find(lli a)
{
if(par[a]!=par[par[a]])
{
par[a]=find(par[a]);
}
return par[a];
/**************************************end**********************************
**************************************practice questions ****************************
