graphdisjoint-setsdisjoint-union

mother vertex using disjoint dataset in directed graph


I had the solution of classical Mother vertex problem using DSU (disjoint data set). I have used path compression.

i wanted to know if it is correct or not.I think time complexity O(E log(V)).

the solution proceeds as

  1. initialise each vertex's parent as it self
  2. as soon as a edge comes, try to join them. note that 1->2 can't be merged if 2 already has some other parent! like if graph is 1->2 , 3->4 , 2->4
  3. here edges 1->2 merge as par[1] = par[2]= 1 and 3->4 merge as par[3]= par[4] =3.
  4. when it comes to merge 2->4, we can't since par[4]!=4, aka, it has some other incoming edge, out of this group.
  5. atlast, all the parent vertices are checked, if they are all equal then, mother vertexos present.

code is :

  class dsu
{
    public:
  int cap;
  vector<int> par;
  
  dsu(int n)
  {
      cap = n; 
      par.resize(cap);
      for(int i=0;  i<cap; i++)
       par[i] = i;
  }
  
  int get(int a)
  {
      while(a!= par[a])
      {
          par[a] = par[par[a]];
          a = par[a];
      }
      return a;
  }
  void join(int a, int b)
  {
        a= get(a);
      int pb= get(b);
      if(pb!=b)
       return ;
       par[pb] = a;
       
  }
  
  
};

int findMother(int n, vector<int> g[]) 
{ 
    // Your code here   
    // do disjoint data set, if everyone;s parent is same woohla! i have found the mother vertex
    
    dsu arr(n);
    
    for(int i=0; i< n; i++)
    {
       for(auto a: g[i])
        {
        arr.join(i,a);}
    }
    
    int mother = arr.get(0);
    for(int i=1; i<n; i++)
    {
        if(mother != arr.get(i))
        return -1;
        
    }
    
    return mother;
    
    
} 

Solution

  • after some research I have fount out that, it is correct. It can be used to find the mother vertex .