Reputation: 31
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