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

Question

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

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

解决方案如下

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

代码是：

  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

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