Implementation (Part 1)

Lesson 5 of 9 in Coddy's Kruskal's Algorithm - Graph Algorithms course.

We start with union-find, the cycle-detection engine.

Challenge

Medium

Kruskal's cycle test relies on union-find. Let's build that first, using it to count connected components.

Write a function named countSets that takes n and the flat edges array (triples [u, v, w, ...], undirected; ignore the weights here) and returns the number of connected components, computed with union-find.

For example, with 4 vertices and edges [0,1,5, 2,3,5] there are 2 components: {0,1} and {2,3}.

Try it yourself

#include <stdlib.h>

int countSets(int n, int* edges, int edges_size) {
    // Write code here
    return 0;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Kruskal's Algorithm - Graph Algorithms

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2