Minimum Spanning Tree Kruskal's Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array for union-find.

DSA C

for (int i = 0; i < n; i++) {
    parent[i] = [1];
}

Drag options to blanks, or click blank then click option'

A-1

B0

Ci

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 causes incorrect union-find behavior.

Using -1 or n as parent values breaks the find operation.

Each node is initially its own parent, so parent[i] = i.

2fill in blank

medium

Complete the code to find the root parent of a node with path compression.

DSA C

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

Drag options to blanks, or click blank then click option'

Aparent[parent[x]]

Bfind(parent, parent[x])

Cx

Dx + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x causes infinite recursion.

Using parent[parent[x]] misses path compression.

Path compression sets parent[x] to the root found by recursive find call.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets.

DSA C

void unionSets(int parent[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        parent[[1]] = rootY;
    }
}

Drag options to blanks, or click blank then click option'

ArootY

By

Cx

DrootX

Attempts:

3 left

💡 Hint

Common Mistakes

Using x or y instead of root parents causes incorrect unions.

Assigning parent[rootY] = rootX merges sets incorrectly.

We set the parent of rootX to rootY to merge the sets.

4fill in blank

hard

Fill both blanks to correctly sort edges by weight using qsort.

DSA C

int compare(const void *a, const void *b) {
    struct Edge *edgeA = (struct Edge *)[1];
    struct Edge *edgeB = (struct Edge *)[2];
    return edgeA->weight - edgeB->weight;
}

Drag options to blanks, or click blank then click option'

Aa

Bb

C*a

D*b

Attempts:

3 left

💡 Hint

Common Mistakes

Dereferencing a or b before casting causes errors.

Swapping a and b changes sort order.

Cast void pointers a and b to Edge pointers to compare weights.

5fill in blank

hard

Fill all three blanks to add an edge to MST and update total weight.

DSA C

if (find(parent, edges[i].src) != find(parent, edges[i].dest)) {
    unionSets(parent, [1], [2]);
    mstEdges[[3]] = edges[i];
    totalWeight += edges[i].weight;
    count++;
}

Drag options to blanks, or click blank then click option'

Aedges[i].src

Bedges[i].dest

Ccount

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of count to index mstEdges overwrites edges.

Swapping src and dest in unionSets causes wrong unions.

Union the source and destination nodes, add edge at index count, then increment count.