I have a vector of vector of strings of size == 2 with the following format
vector<vector<string>> equations;
where equations[i]={"Hi", "I am"}; I want to make a disjoint union of the two strings "Hi" and "I am" for all the values of i. So I tried to make the same using map, and was failing at some many test cases. I want to find the parent of the strings
Ex:{{"a","b"},{"b","c"},{"a","d"}} should give parent for all the elements as any
element in the equations vector Ex: "a";
Is there any material for the same? or any reference to which I can refer to? or the code for this problem?
map<string,int> siz;
string &find(map<string,string> &mp,string &a)
{
if(mp[a]==a)
return a;
return mp[a]=find(mp,mp[a]);
}
void Union(map<string,string> &mp,string &a,string &b)
{
a=find(mp,a);
b=find(mp,b);
if(a==b)
return;
else
{
if(siz[a]>siz[b])
{
mp[b]=a;
siz[a]+=siz[b];
}
else
{
mp[a]=b;
siz[b]+=siz[a];
}
}
}
void get_parent(vector<vector<string>> &equations,vector<string> &ele)
{
map<string,string> parent;
for(int i=0;i<equations.size();i++)
{
parent[equations[i][0]]=equations[i][0];
parent[equations[i][1]]=equations[i][1];
siz[equations[i][0]]=1;
siz[equations[i][1]]=1;
}
for(int i=0;i<equations.size();i++)
{
Union(parent,equations[i][1],equations[i][0]);
}
for(int i=0;i<ele.size();i++)
cout<<(parent[ele[i]]);
}