Stack Overflow
Stack Overflow

Questions tagged [union-find]

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

184 questions
27
votes
10 answers

Union-find expressed as a social network

This is an interview question that I am trying to answer: Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at…
template boy
  • 10,230
  • 8
  • 61
  • 97
26
votes
1 answer

Avoiding IORefs in pure code

I noticed that Data.UnionFind uses the IO monad to provide pointers via IORefs. I imagine everyone happily calls unsafePerformIO when using it locally in pure code, since the data structure is so well understood, but .. Is there a canonical cleaner…
Jeff Burdges
  • 4,204
  • 23
  • 46
22
votes
3 answers

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 why?
vinter
  • 466
  • 1
  • 3
  • 13
19
votes
3 answers

Why does the weighted quick union algorithm consider the sizes of the tree instead of their heights?

I was watching Robert Sedgewick's video on improvements to quick union. (https://youtu.be/sEo6LlPxpHE?t=267) There he uses size of the tree rather than the height. Actually the problem is finding the root node . finding will be difficult if the…
Harish Kayarohanam
  • 3,886
  • 4
  • 31
  • 55
17
votes
3 answers

Is the Union-Find (or Disjoint Set) data structure in STL?

I would have expected such a useful data structure to be included in the C++ Standard Library but I can't seem to find it.
Ritwik Biswas
  • 1,329
  • 1
  • 13
  • 18
14
votes
4 answers

Union-find data structure

For many problems I see the solution recommended is to use a union-find data structure. I tried to read about it and think about how it is implemented (using C++). My current understanding is that it is nothing but a list of sets. So to find which…
Asha
  • 11,002
  • 6
  • 44
  • 66
14
votes
2 answers

Why path compression doesn't change rank in UnionFind?

I'm looking at the implementation of UnionFind with union by rank and path compression from here http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests (it's pretty much the same pseudo-code as in CLRS) and don't understand…
synapse
  • 5,588
  • 6
  • 35
  • 65
14
votes
4 answers

Union find implementation using Python

So here's what I want to do: I have a list that contains several equivalence relations: l = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]] And I want to union the sets that share one element. Here is a sample implementation: def union(lis): lis =…
thomas zhang
  • 165
  • 1
  • 1
  • 7
12
votes
3 answers

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. Backwash is appearance of the crossed sites as full…
curio
  • 121
  • 1
  • 4
12
votes
8 answers

Union-Find: Successor with delete

I'm trying to solve this problem of Union-Find which goes like Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form: Remove x from S Find the successor of x: the smallest y in S such…
Cyclotron3x3
  • 2,188
  • 23
  • 40
11
votes
2 answers

Union-Find: retrieve all members of a set efficiently

I'm working with an union-find algorithm. In the first part of my program, the algorithm computes a partition of a big set E. After that, I want to retrieve all the members of the set S, which contains a given node x. Until now, naively, I was…
HNoob
  • 591
  • 4
  • 13
11
votes
1 answer

Equivalence classes and union/find in a functional language

For an automata algorithm, I require a fast Union-Find data structure in a functional language. Since I need to formally prove the correctness of the data structure, I would prefer a simple structure. What I am trying to do is to compute the…
Manuel Eberl
  • 7,858
  • 15
  • 24
10
votes
1 answer

Union-find in a graph structure

I have a record describing a graph as sets of nodes and edges: data MyGraph a = MyGraph { nodes :: Set a, edges :: Set (a,a), components :: UnionFindM a -- ? } emptyGraph = MyGraph{ nodes = empty, edges = empty, components = emptyUnionFind…
pascal
  • 2,623
  • 2
  • 20
  • 30
10
votes
4 answers

Weighted Quick-Union with Path Compression algorithm

There is a "Weighted Quick-Union with Path Compression" algorithm. The code: public class WeightedQU { private int[] id; private int[] iz; public WeightedQU(int N) { id = new int[N]; iz = new int[N]; for(int…
Aleksei Chepovoi
  • 3,915
  • 8
  • 39
  • 77
9
votes
2 answers

How do path compression and union by rank complement each other?

I have been reading about union-find problem. The two main improvements are path compression and union by rank. As far as I understand union by rank is used to determine how to combine disjoint trees. If we have two disjoint trees T1 and T2, then we…
Hermon
  • 114
  • 1
  • 5
1
2 3
…
12 13