Questions tagged [union-find]
A union/find data structure is a data structure used for maintaining a partition of a set.
181
questions
-2
votes
1
answer
36
views
My program is putting out garbage values when asked to print union of two sets. Can someone assist in this case
My program is putting out garbage values when asked to print union of two sets. Can someone assist in this case. The unique elements of the second array are not getting reflected in the result.
My ...
-1
votes
0
answers
23
views
LC 1135. Connecting Cities With Minimum Cost - Can someone help me debug this Minimum Spanning Tree problem on LeetCode?
Problem: https://leetcode.com/problems/connecting-cities-with-minimum-cost/
There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, ...
3
votes
1
answer
58
views
Finding connected components in a DYNAMIC Graph
When it comes to finding connected components in a graph we can use DFS or DSU. Does there exist an algorithm which is stable to a changing graph, where node can be added, edge can be removed, node ...
0
votes
0
answers
53
views
Monte Carlo Simulation of Percolation is not Giving Expected Results
I've started working my way through the Princeton Algorithms course on Coursera. The course uses Java, but I decided to follow along with C as it is what I am most comfortable with. One of the ...
2
votes
1
answer
56
views
Can I detect a cycle in an undirected graph with n edges in O(n log*(n)) ? ( log*(n) is log star function )
I have the following algorithm for detecting a cycle in an undirected graph with a set E of n edges :
for each unvisited edge (u, v) in E:
{
if(Find(u) = Find(v)) // u and v belong to the same set ...
-3
votes
5
answers
125
views
How to solve manager peer problem question?
I was asked below question in google interview but could not answer it. I did google search but could not find any correct solution for this problem. Can you please help me to provide a solution for ...
2
votes
1
answer
45
views
columns of numbers and union-find structure
The problem:
Put the numbers from 1 to M into M columns. At the beginning column i contains only number i. Then, perform N queries of two possible types:
A i j: remove all numbers from column i and ...
0
votes
0
answers
29
views
Depth First Search vs Union-Find by Rank -- Mesh Islands
I am trying to determine what parts of a 3D Mesh are disjointed, if any, and create a Dictionary of lists containing the Disjointed part's values (verts, tris, UV's, etc.) to rebuild.
I have ...
1
vote
0
answers
60
views
What is the difference between these 2 implementations of quick find?
I was learning about quick find and made a very basic implementation in java but my union function was not working properly when I initially implemented it. I made some changes and it started working ...
5
votes
1
answer
463
views
Is this Union Find really O(n) as they claim?
I am solving a problem on LeetCode:
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. So ...
0
votes
0
answers
52
views
Constant time lookup for unions and finds
I have a homework question that asks us to show that, for size-based union-find with path compression: if all unions are done before all finds, it takes O(n) time to do O(n) unions and O(n) finds.
My ...
3
votes
1
answer
262
views
Optimize Union Find (Disjoint Set Union) implementation
I have implemented a Disjoint Set Union in C++ for a Kattis problem. However, my solution is inefficient, as I get TLA (Time Limit Exceeded) for the first hidden test case. Can anyone spot an ...
0
votes
0
answers
39
views
Hoshen-Kopelman Algorithm MatLab Implementation
First of all, I'm not 100% sure if Matlab is allowed on stack overflow; if I'm violating the rules tell me and I'll delete the question.
I'm currently studying percolation on a 2D surface (using a ...
0
votes
0
answers
51
views
Aggregating matched points for bundle adjustment using networkx union find
I am trying to solve a bundle adjustment problem. I have calculated an array that contains point correspondences for every image that overlaps.
matchMat = getMatchMat(imgs,occupancy)#matchMat[i,j]=...
3
votes
3
answers
94
views
Do the order of edges matter in union find?
I am learning union-find and to understand it better, I have written a small program:
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
vector<int>...
0
votes
1
answer
126
views
Returning the right number of islands using Union Find
I am solving a question on LeetCode.com called Number of Islands:
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is ...
0
votes
1
answer
76
views
How do I import UnionFind<T> to IntelliJ? (Java)
I want to import this UnionFind- class to my IntelliJ project. But I get a Maven error I do not understand. When I try and type import org.jgrapht.alg.util.UnionFind<T>; in the beginning of my ...
1
vote
1
answer
113
views
UnionFind with weighted Quick Union (a.k.a Union by rank)
In the Union Find algorithm provided by LeetCode's tutorial, it seems the weight (rank) of the tree is only incremented when merging two equal weight subsets, however not the case when one is greater ...
-1
votes
2
answers
32
views
Leetcode Number of Province not passing edge case last few edge case
I try using the Union find method for this question but not passing this case, could somebody may be give me an insight to why that is?
find() : for find method there is path compression
union() : for ...
1
vote
1
answer
119
views
Leetcode 1584. How can I improve my Kruskal&Union Find algorithm to make it faster?
The question was on Leetcode 1584. Min Cost to Connect All Points. My answer to this question is:
class Solution {
public int minCostConnectPoints(int[][] points) {
List<int[]> list =...
-2
votes
1
answer
196
views
Java algorithm problem: output one of the two connected paths [closed]
/**
* The Problem:
*
* We have a list of tasks. Each task can depend on other tasks.
* For example if task A depends on task B then B should run before A.
*
* Implement the "...
0
votes
0
answers
12
views
How does the Root Method Work in Quick-Union? [duplicate]
I've recently been studying the Princeton Algorithms course on Coursera. The course begins by teaching an algorithm called Quick-Union to solve the Dynamic Connectivity Problem..
While I understand ...
0
votes
3
answers
264
views
Algorithm to find cluster of nodes that are connected
I'm working with 3d data and am provided with a list of vertices that are connected to each other. The data has the following format:
faces = [
(0, 1, 2),
(1, 3, 2),
(3, 5, 6),
(5, 7, ...
0
votes
0
answers
32
views
Union-find algorithm not working for finding number of connected components(HackerEarth)
I tried implementing Union-find algorithm for finding number of connected components in a graph.
Problem link - https://www.hackerearth.com/problem/algorithm/connected-components-in-a-graph/
Problem ...
1
vote
0
answers
35
views
Modified Union Find Data Structure
connected: takes two arguments s and t and returns true if they are in the same set and false otherwise.
combine: takes two arguments s and t and creates a union of the two sets that contain s and t ...
1
vote
1
answer
70
views
Implementation of textbook Union-Find algorithm doesn't work
I have two implementations of union-find: one that I've come up on my own (it works) and another that is based on the textbook explanation (surprisingly, does not work). While I am debugging the ...
1
vote
1
answer
52
views
Enumerating equivalence classes
What I have: an equivalence relation on the set {1,...,n}, given as the full list of equivalent pairs (a,b) (this is already transitive; no need to compute a transitive closure). n is large (say, a ...
0
votes
1
answer
45
views
Union find algorithm in Kruskals algorithm
How does these two functions work ?
The time complexity of the function find is O(log n) assuming that the length
of each chain is O(log n). In this case, the functions same and unite also work in
O(...
3
votes
2
answers
279
views
How to implement a union-find (disjoint set) data structure in Coq?
I am quite new to Coq, but for my project I have to use a union-find data structure in Coq. Are there any implementations of the union-find (disjoint set) data structure in Coq?
If not, can someone ...
-1
votes
2
answers
96
views
Memory limit exceded error to find maximum value from each componenet in graph
Here is the question:
exmaple:
5
12 34 10 7 8
3
1 2
2 3
3 1
Output:
56
Groups are formed as: [1,2,3][4][5].
Maximum collection is 56 (collected by volunteer 1, 2, and 3).
My logic was to run a dfs ...
1
vote
1
answer
59
views
How to show top to bottom leaks in my path
I used the percolation class from the algs4.jar library, where you can simulate a whole labyrinth and see where the leaks are. I want to show the leaks that are from top to bottom, but now I get to ...
0
votes
1
answer
1k
views
union by size vs union by rank in disjoint-set algorithm
The question in short: does union by rank work only in some circumstance?
For example, the input is:
(1, 2), (3,4), (3,5), after we run a disjoint-set algorithm on them:
one of the correct output ...
0
votes
0
answers
66
views
Code for implementation of Kruskal's algo produces wrong o/p
Below is the program to find cost of minimum spanning tree, the graph is represented as ArrayList<ArrayList<Integer>>. So first I stored all the edges in a minHeap and polled them by ...
3
votes
2
answers
147
views
Dynamic union find algorithm in Prolog
Lets assume I have sets S1,..,Sn and we want to find
smallest covers C1,..,Cm so that in each cover there are never disjoint
connected components.
for example with the sets S1=[X,Y], S2=[Y,Z], S3=[T] ...
0
votes
1
answer
226
views
Union Find - Why we are checking Size for Weighted Quick Union
I was going through Princeton's Algorithms course on Coursera.
In the Union find section, for Weighted Quick union, we merge trees depending upon which tree is smaller in terms of Size.
However, I ...
0
votes
0
answers
65
views
Self-referential struct in c++ for union-find
The following is a Java implementation of union-find, and I wish to replicate the same in C++:
class v_rank{
int position, rank;
v_rank parent;
public v_rank(int position){
this....
1
vote
1
answer
153
views
Will applying Path compression to Union Find always results in a flat tree, If so, Why?
The below images show a Union find Problem solved by rank with path compression. If you don't understand my handwriting then read the description below to understand what I have done.
Description:
...
0
votes
1
answer
531
views
Union Find in Java
I am trying to implement the union-find algorithm. Basically the part of the algorithm that I am struggling with is the union part. What is supposed to happen is that there is a list of numbers (...
0
votes
1
answer
186
views
Union-find algorithm does not return expected result
I implemented the following union-find algorithm using this example:
import numpy as np
class UnionFind(object):
def __init__(self, edges):
self.edges = edges
self.n_edges = np....
2
votes
1
answer
313
views
Fixing Karger's min cut algorithm with union-find data structure
I was trying to implement Karger's min cut algorithm in the same way it is explained here but I don't like the fact that at each step of the while loop we can pick an edge with it's two endpoints ...
0
votes
1
answer
98
views
finding if there is a way from the top to a specific element in 2-dimensional array
I have a 2-dimensional array, I want to check if there is any way from the top row to a specific element in the array.
The way means: that there is continuously connected 1 from top to the element.
...
10
votes
2
answers
4k
views
How to handle the backwash problem in percolation without creating an extra WUF object or using a method with complexity >= O(n)?
I am taking the Algorithms, Part I course on coursera and am stuck on a bonus question of the first assignment. I have already submitted my solution and got my marks. This is just for curiosity.
...
-1
votes
1
answer
94
views
Union Find Algorithm - reading other's code
I was trying to understand the code on https://www.geeksforgeeks.org/union-find/.
I am not sure whether "parent" in the highlighted part refers to a "defaultdict" object that the user needs to input....
19
votes
3
answers
7k
views
Can we detect cycles in directed graph using Union-Find data structure?
I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not?
If yes, then how? and
If we can't, then ...
4
votes
1
answer
3k
views
Is the disjoint-set data structure implemented natively in Java?
I searched for a native implementation of the disjoint-set data structure in Java. But I didn't find one, only in external libraries.
Did I miss it or does it actually not exist?
0
votes
1
answer
450
views
proof of time complexity of union find with path compression
The Wikipedia page: wikipedia page states that
If m operations, either Union or Find, are applied to n elements, the total run time is O(m log*n).
The detailed analysis arrived at this result is :...
3
votes
2
answers
350
views
Iterating over classes in a disjoint set data structure
I've implemented a disjoint set data structure for my program and I realized I need to iterate over all equivalence classes.
Searching the web, I didn't find any useful information on the best way to ...
0
votes
1
answer
509
views
Find the number of connected components in undirected graph using Union Find
I've been staring at this algorithm for a while but couldn't spot what I've missed.
Logic:
Init all isolated components
union frm, to component in each edge and decrement # components if those ...
1
vote
1
answer
1k
views
What are the advantages and disadvantages of union-find and breadth first search?
What are the advantages and disadvantages of union-find and breadth first search?
example: theoretical algorithm complexity, application differences, and so on.
1
vote
0
answers
86
views
How to detect a cycle in a directed graph using the union-find algorithm [duplicate]
Can I apply the union-find algorithm for the detecting a cycle in a directed graph other than Depth First Search (DFS)?
I know that we can apply the union-find algorithm for the detecting cycle in a ...