Questions tagged [union-find]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
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 ...
user avatar
  • 135
3 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1,835
5 votes
4 answers
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 ...
user avatar
  • 665
2 votes
1 answer
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: ...
user avatar
  • 21
12 votes
1 answer
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 ...
user avatar
  • 91
4 votes
1 answer
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 ...
user avatar
  • 331
2 votes
2 answers
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[]...
user avatar
  • 29
0 votes
2 answers
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
5 votes
3 answers
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: ...
user avatar
3 votes
1 answer
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 ...
user avatar
3 votes
1 answer
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. ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 131
1 vote
2 answers
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 ...
user avatar
7 votes
1 answer
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 ...
user avatar
  • 22.4k
2 votes
2 answers
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 ...
user avatar
7 votes
1 answer
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 ...
user avatar
6 votes
2 answers
544 views

Disjoint set in Haskell

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: "...
user avatar
8 votes
1 answer
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. ...
user avatar
  • 350
4 votes
2 answers
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 ...
user avatar
  • 41
7 votes
1 answer
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 <...
user avatar
5 votes
2 answers
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 ...
user avatar
5 votes
1 answer
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, ...
user avatar
  • 53
1 vote
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
6 votes
1 answer
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: ...
user avatar
  • 91
6 votes
1 answer
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. ...
user avatar
3 votes
2 answers
4k views

Disjoint set implementation as linked list

I have just 'wrote' a linked list implementation of Disjoint Sets. This is the changed version of Bob Tian's implememnation. Can you take a look and tell me if there is something missing ? For ...
user avatar
  • 305