在有向图中使用不相交数据集的母顶点

Question

我使用 DSU（不相交数据集）解决了经典的母亲顶点问题。我使用了路径压缩。

我想知道它是否正确或 not.I 认为时间复杂度 O(E log(V))。

求解过程为

将每个顶点的父级初始化为自身
一有优势就加入他们。请注意，如果 2 已经有其他父级，则 1->2 不能合并！就像图形是 1->2 , 3->4 , 2->4
此处边 1->2 合并为 par[1] = par[2]= 1 和 3->4 合并为 par[3]= par[4] =3.
当谈到合并 2->4 时，我们不能，因为 par[4]!=4，也就是说，它有一些其他传入边，不在这个组中。
最后，检查所有父顶点，如果它们都相等，则存在母顶点。

代码是：

  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;
    
    
}

Answer 1

经过一些研究，我发现这是正确的。可以用来找母顶点。

在有向图中使用不相交数据集的母顶点

mother vertex using disjoint dataset in directed graph

graph

disjoint-union

disjoint-sets