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
- initialise each vertex's parent as it self
- 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
- here edges 1->2 merge as par[1] = par[2]= 1 and 3->4 merge as par[3]= par[4] =3.
- 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.
- 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;
}
after some research I have fount out that, it is correct. It can be used to find the mother vertex .