Questions tagged [union-find]
A union/find data structure is a data structure used for maintaining a partition of a set.
31
questions
0
votes
2
answers
53
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
178
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
3
votes
1
answer
80
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 ...
- 133
0
votes
0
answers
71
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
5
votes
4
answers
540
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 ...
- 685
2
votes
1
answer
71
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
779
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 ...
- 101
4
votes
1
answer
233
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
2
votes
2
answers
91
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
747
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
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
5
votes
3
answers
2k
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
3
votes
1
answer
278
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
116
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
164
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
2
answers
407
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
1
answer
589
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.9k
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 ...
- 172
7
votes
1
answer
380
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 ...
- 172
6
votes
2
answers
613
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: "...
- 277
8
votes
1
answer
184
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
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 ...
- 41
7
votes
1
answer
472
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 <...
- 71
5
votes
2
answers
520
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
1
answer
256
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
2
votes
1
answer
137
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
...
- 195
2
votes
1
answer
525
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
2
votes
0
answers
295
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
6
votes
1
answer
9k
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
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. ...
- 221
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 ...
- 305