Xiao
Xiao

Reputation: 31

Disjoint Set Union

I was solving a problem of Hackerrank in Graphs a particular question https://www.hackerrank.com/challenges/journey-to-the-moon/problem

I applied DSU but the answer is wrong even though the code is working for some test cases.

void make(int item)
{
    parent[item]=item;
    siz[item]=1;
}
int find(int a)
{
    if(parent[a]==a)
        return parent[a];
    else
    {
        parent[a]=find(parent[a]);
        return parent[a];
    }
}
void Union(int a,int b)
{
    a=find(a);
    b=find(b);
    if(a==b)
        return;
    else
    {
        if(siz[a]>siz[b])
        {
            parent[b]=a;
            siz[a]+=siz[b];
        }
        else
        {
            parent[a]=b;
            siz[b]+=siz[a];
        }
    }
}
int journeyToMoon(int n, vector<vector<int>> astronaut)
{
    for(int i=0;i<n;i++)
    {
        make(i);
    }
    for(int i=0;i<astronaut.size();i++)
    {
        Union(astronaut[i][0],astronaut[i][1]);
    }
    map<int,int> mp;
    for(int i=0;i<n;i++)
    {
        mp[parent[i]]++;
    }
    int cmp=0;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        for(auto jt=mp.begin();jt!=mp.end();jt++)
        {
            if(jt==it)
                continue;
            else
            {
              cmp=cmp+it->second*jt->second;  
            }
        }
    }
return cmp/2;
}

It is giving partially correct I think the logic is right but the solution has some problem

Test Case : 10 7 0 2 1 8 1 4 2 8 2 6 3 5 6 9 My Output->29 Actual Output->23

Upvotes: 1

Views: 182

Answers (0)

Related Questions