Disjoint Union of Strings

107 views Asked by At

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]]);
}
0

There are 0 answers