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
1answer
26 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 ...
2
votes
1answer
20 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
65 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
180 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
142 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 ...
1
vote
2answers
345 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
157 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
238 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
156 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. ...
5
votes
2answers
965 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
319 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 <...
4
votes
2answers
274 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
172 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
48 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
119 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 ...
1
vote
0answers
407 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
193 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 ...
5
votes
1answer
7k 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
2k 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
3k 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 ...