We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Journey to the Moon
  5. Discussions

Journey to the Moon

Sort by

recency

|

519 Discussions

|

  • mraj8370
     + 0 comments

    class UnionFind { public: vector parent, size;

    UnionFind(int n) {
    parent.resize(n);
    size.resize(n, 1);
    iota(parent.begin(), parent.end(), 0);
}

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px == py) return;
    if (size[px] < size[py]) swap(px, py);
    parent[py] = px;
    size[px] += size[py];
}

    };

    long journeyToMoon(int n, vector>& astronaut) { UnionFind uf(n);

    for (auto &p : astronaut) {
    uf.unite(p[0], p[1]);
}

unordered_map<int,int> countrySize;
for (int i = 0; i < n; i++)
    countrySize[uf.find(i)]++;

long total = n;
long result = 0;
for (auto &[_, sz] : countrySize) {
    result += (long)sz * (total - sz);
    total -= sz;
return result}

    can anyone suggest what's is wrong one test case is faling?

    }
return result;

    }

  • villeyvince
     + 0 comments

    Nice breakdown of the issue and clear grasp of how to identify connected components for the Journey to the Moon problem on HackerRank via DFS or union-find roller lip . Your suggestion to use prefix sums when calculating cross-country pairs is spot on and avoids overflow issues too.

  • kbssj1
     + 0 comments

    Javascript

    let cnt = 0;
function Dfs(visited, tree, i) {
    if (visited[i]) {
        return;
    }
    
    visited[i] = true;
    ++cnt
    if (tree[i]) {
        for (let v of tree[i]) {
            Dfs(visited, tree, v);
        }
    }
}

/*
 * Complete the 'journeyToMoon' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY astronaut
 */

function journeyToMoon(n, astronaut) {
    // Write your code here
    let tree = {};
    for (const [a1, a2] of astronaut) {
        tree[a1] = tree[a1] ?? new Set();
        tree[a2] = tree[a2] ?? new Set();
        tree[a1].add(a2);
        tree[a2].add(a1);
    }
    let a = [];
    let ans = 0;

    for (let i=0;i<n;++i) {
        if (!visited[i]) {
            Dfs(visited, tree, i);
            a.push(cnt);
            cnt = 0;
        }
    }
    
    for (let i=0;i<a.length;++i) {
        for (let j=i+1;j<a.length;++j) {
            ans += a[i] * a[j];
        }
    }
    return ans;
}

  • qiwang001
     + 0 comments

    Using union_find is more efficient than using graph.

  • write2piyushkum1
     + 1 comment

    Test case 11 does not pass. All others pass.

    Solution using DFS.

    public static int journeyToMoon(int n, List<List<Integer>> astronaut) {
        // Write your code here
        Map<Integer, List<Integer>> adj = buildAdjList(n, astronaut);

        Set<Integer> visited = new HashSet<>();
        Set<Set<Integer>> countries = new HashSet<>();
        for (int i=0;i<n;i++) {
            if (!visited.contains(i)) {
                Set<Integer> astronautInCountry = new HashSet<>();
                
                dfsVisit(adj, i, visited, astronautInCountry);
                
                countries.add(astronautInCountry);
            }
        }
        long result = 0;
        for (Set<Integer> country : countries) {
				// If choose 1st atronaut from country, there are (n - country.size()) astronaut to choose 2nd.
            result += (country.size() * (n - country.size()));
        }
        return (int)(result / 2);
    }
    
    private static void dfsVisit(final Map<Integer, List<Integer>> adj, int node, Set<Integer> visited, Set<Integer> astronautInCountry) {
        visited.add(node);
        astronautInCountry.add(node);
        
        for (int neighbor : adj.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsVisit(adj, neighbor, visited, astronautInCountry);
            }
        }
    }
    
    private static Map<Integer, List<Integer>> buildAdjList(int n, List<List<Integer>> astronaut) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        
        for (int i=0; i<n; i++) {
            adj.put(i, new ArrayList<>());
        }
        for (List<Integer> edge : astronaut ) {
            adj.get(edge.get(0)).add(edge.get(1));
            adj.get(edge.get(1)).add(edge.get(0));
        }
        
        return adj;
    }