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
4
votes
1answer
73 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 ...
2
votes
2answers
79 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[]...
0
votes
2answers
119 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 ...
3
votes
2answers
76 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 ...
5
votes
3answers
923 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: ...
3
votes
1answer
132 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
1answer
70 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
1answer
107 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 ...
1
vote
2answers
301 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 ...
7
votes
1answer
322 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 ...
2
votes
2answers
965 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 ...
7
votes
1answer
189 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 ...
6
votes
2answers
366 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: "...
8
votes
1answer
164 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. ...
4
votes
2answers
1k 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 ...
7
votes
1answer
369 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 <...
5
votes
2answers
427 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 ...
5
votes
1answer
222 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, ...
1
vote
0answers
49 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 ...
2
votes
1answer
126 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 ...
2
votes
1answer
453 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 ...
2
votes
0answers
217 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 ...
6
votes
1answer
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: ...
6
votes
1answer
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. ...
3
votes
2answers
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 ...