Skip to main content

Union Find


Here is my implementation of Union Find with Path Compression in Python.



class uf:
 def __init__(self,numnodes):
  self.r = [1] * (numnodes)
  self.p = []
  for i in range(n):
   self.p.append(i)
 
 def j(self,a,b):
  if a == b:
   return
  a=self.root(a)
  b=self.root(b)
  if a == b:
   return
  if self.r[a] > self.r[b]:
   self.r[a]+=self.r[b]
   self.p[b]= self.p[a]
  else :
   self.r[b]+=self.r[a]
   self.p[a] = self.p[b]
   
  
  
 def root(self,a):
  
  while True:
   if self.p[a]==a:
    break
   else:
    self.p[a] =self.p[self.p[a]]
    a = self.p[a]
  return a
 def q(self,a,b):
  if self.root(a) == self.root(b):
   return True
  else:
   return False

Comments

Popular posts from this blog

Solution to UVa 10608 - Friends in C++ using Union Find

This is the solution to this UVa problem Code #include <iostream> #include <iostream> #include<bits/stdc++.h> #define pb push_back #define T 50005 using namespace std; int p[T]; int r[T]; void ini(int n){ for(int i=0;i<n;i++){ p[i]=i; r[i]=1; } } int root(int a){ while(p[a]!=a){ p[a]=p[p[a]]; a=p[a]; } return a; } void joint(int a,int b){ if (a==b) return; a=root(a); b=root(b); if (a == b) return; if(r[a]>r[b]){ r[a]+=r[b]; p[b]=a; return; } r[b]+=r[a]; p[a]=b; } bool query(int a, int b){ return p[a]==p[b]; } int main() { std::ios::sync_with_stdio(false); int breaker; cin>>breaker; int test=0; while(1){ test++; if(test>breaker) break; int n,m; cin >> n>>m; if(n==0 && m==0) break; ini(n); while(m--){ int i,j; cin>>i>>j; joint(i-1,j-1); } int counter=0; int maxi=0; for(int i =0;i<n;i++){ maxi=max(maxi,r[i]); } cout&