1

我正在解决图中的 Hackerrank 问题一个特定的问题https://www.hackerrank.com/challenges/journey-to-the-moon/problem

我应用了 DSU，但即使代码适用于某些测试用例，答案也是错误的。

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;
}

它给出了部分正确我认为逻辑是正确的，但解决方案有一些问题

测试用例：10 7 0 2 1 8 1 4 2 8 2 6 3 5 6 9 我的输出->29 实际输出->23

4

0 回答 0