Questions tagged [union-find]
A union/find data structure is a data structure used for maintaining a partition of a set.
31 questions
3
votes
1
answer
173
views
C++ two-phase path-compression quick-union union find over indices
This is my first C++ class, implementing union find. I’ve tested the implementation very shoddily by checking that unifying two points connects them, and that works. I did a first draft in Python and ...
- 509
1
vote
2
answers
405
views
Union-find disjoint set solution to calculating sizes of connected components
I'm given a distance and a list of points in a plane, where I have to return a sorted list of the size of each connected component where each edge is shorter or equal to the distance threshold.
I've ...
3
votes
1
answer
298
views
Percolation threshold simulation using C++
I am studying Algorithms by Princeton University. The first week assignment is to simulate percolation by using Java.
https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php
...
- 135
4
votes
1
answer
180
views
Weighted Union-Find class
For a final project I used a weighted union-find and decided to implement it in Python. I wrote it to be as general as possible so it's very portable. I do plan on looking into path compression to ...
- 143
4
votes
4
answers
795
views
Disjoint-set data structure (C++)
I'm an intermediate-level C++ programmer aiming to write reference-quality code. I hope to learn about any mistakes in this piece of code and blind spots in my understanding of concepts. Notes:
The ...
- 1,369
2
votes
1
answer
114
views
Leetcode 1584. How to make my Kruskal&Union Find algorithm faster?
The question was on Leetcode 1584. Min Cost to Connect All Points. My answer to this question is:
...
- 21
12
votes
1
answer
1k
views
How Rusty is my generic union-find implementation?
I decided to implement a DisjointSet<T> data structure myself in Rust, with no dependencies except for std, for the ...
- 166
4
votes
1
answer
318
views
K-clustering algorithm using Kruskal MST with Disjoint Set in place to check for cycles
here below a working implementation that finds the minimal distance between k(set =4 below) clusters in a graph.
I have doubts mainly on the implementation of the ...
- 515
2
votes
2
answers
142
views
Different approach Union Find
I am studying algorithms and I did this "Union Find Like" algorithm.
I have one array of objects with a reference and I make the union pointing to the same reference instead of have two int[]...
- 29
0
votes
2
answers
1k
views
Union find using unordered map and templates in C++
I tried to implement union find (disjoint set data structure) algorithm in C++. There I used unordered_map data structure. Is there a better way of doing this using any other data structure.
While ...
- 113
3
votes
2
answers
112
views
Integer index based Union Find with path compression strategy
I've created an integer index based union find implementation in C#, and am looking for some feedback. Unit tests have been written with NUnit. Some questions I am considering:
Can the implementation ...
- 145
5
votes
3
answers
4k
views
Printing the bits of an integer using bitfields and union
I am given a short int. I need to print the bits of it into two bytes. My code is as follows:
...
- 335
3
votes
1
answer
307
views
Kruskals MST Algorithm
This code computes the Minimum Spanning Tree of a given graph using Kruskals Algorithm.
It works successfully and I have provided test cases within the code.
I would like feedback on code efficiency ...
3
votes
1
answer
162
views
Find cycles in Graph using Union Find Algorithm on Adjacency List
My code detects if a cycle is present in a graph using Union find algorithm with Weighted tree analysis and path compression.
It works and I have included test cases.
...
2
votes
1
answer
209
views
Kruskal MST algorithm
I came up with the following code by following Prof. Sedgewick's lecture on Coursera.
Please review this code and let me know if there is anything that I got wrong in implementing Kruskal's ...
- 131