# Questions tagged [union-find]

A union/find data structure is a data structure used for maintaining a partition of a set.

31 questions
Filter by
Sorted by
Tagged with
76 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
52 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 ...
• 33
48 views

### Implementation for Simple Disjoint Set

Simple Disjoint Set Implementation I had not implemented a DisjointSet before and the following is my attempt at implementing a very simple ...
• 1,835
452 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 ...
• 665
67 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
555 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 ...
• 91
158 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 ...
• 331
88 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
556 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 ...
84 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
1k 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: ...
• 313
259 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 ...
99 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. ...
146 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
1 vote
379 views

### Graph library including minimum spanning tree using Kruskal's Algorithm

I've only ever made small programs. So, I've tried to make something large but easily reusable/extendable. Posted below are the beginnings of a graph library I've written up. One particular point I'd ...
536 views

### Swiftly counting rooms in a floor plan

Inspired by recent questions about counting the rooms in a floor plan (1, 2, 3), here is my attempt to solve the problem with a Swift program. The problem (from “Counting Rooms” on CSES) is: You ...
• 22.4k
3k views

### Finding the size of the largest connected component in a graph

Given this question, which simply can be explained as follows: Given the number of nodes and the number of edges in a graph, find the size of the largest connected component of the graph. If this ...
• 172
341 views

### Performance of C++ Union-Find solution is strangely poor

Problem Summary (USACO Gold 3 February 2016) Given a rectangular coordinate plane of dimensions (A,B), there are N vertical ...
544 views

I think my error-handling here is atrocious, but I'm really new to Haskell so hoping one of you sages can help me out. This program is a command-line tool which you use by typing one of two commands: "...
182 views

### DisjointSet class in Python

I would like to improve my DisjointSet class implementation in Python. I would be grateful for specific advice. I use it in online contests so it must be short, quick and reusable. ...
• 350
2k views

### Weighted union-find with path compression in Python 3

I implemented the Union-Find data structure and would love to receive some feedback about my code. I have just begun programming and welcome any feedback or constructive criticism which would improve ...
• 41
440 views

### Union-Find in C++

A few days ago I start learning C++. This code is a simple Union-Find data structure. Questions: Why can't I use const union_find<T> &uf instead of <...
513 views

### Forming sets from pairs of numbers

I do not want to use a new data structure but the existing APIs in Java. Here's a solution. I am thinking if this can be made simpler. Input say ...
252 views

### Rainfall challenge solution using Union-find

I have tried to implement a solution to the Rainfall challenge based on the suggestions from 200_success♦ (Rainfall challenge). Problem Statement A group of farmers has some elevation data, ...
• 53
1 vote
50 views

### FindUnion data structure used to find the minimum cut of a graph

I am trying to find the bottleneck in my code for computing the minimum cut of a graph. Currently the program runs in about 40 minutes on the test data set linked below (200 nodes and ~2000 edges). I ...
133 views

### DisjointSet with O(1) find and O(1) amortised union

Does this code outperform the common implementation with path-compression and union-by-rank? I'm still okay with a review. GitHub ...
516 views

### Union Find implementation

I am trying to complete this challenge. The user should enter a sequence of instructions, = to link two numbers, and ? to query ...
• 121
261 views

### Union-find implementation

Here are a few questions on my mind: What improvements to the above code can you think of? I want to say new UnionFind(x) where ...
• 149
8k views

### C++ class for disjoint-set/union-find on integers

I have implemented the disjoint-set data structure. The purpose is to group integers together. For example, if I want to find out the groups of integers where each adjacent neighbors are same: ...
• 91
3k views

### UnionFind implementation

The Wikipedia article on the union find problem gives a very simple implementation, which I ported to C# and tested. I know that the code should be, in the aggregate, asymptotically almost linear. ...
• 221