Stack Overflow
Stack Overflow

Questions tagged [disjoint-sets]

Anything related to disjoint sets, i.e. mathematical sets that have no element in common.

Anything related to disjoint sets, i.e. mathematical sets that have no element in common.

194 questions
60
votes
5 answers

Understanding boost::disjoint_sets

I need to use boost::disjoint_sets, but the documentation is unclear to me. Can someone please explain what each template parameter means, and perhaps give a small example code for creating a disjoint_sets? As per the request, I am using…
Amir Rachum
  • 76,817
  • 74
  • 166
  • 248
20
votes
10 answers

Implementing Disjoint Sets (Union Find) in C++

I am trying to implement Disjoint Sets for use in Kruskal's algorithm, but I am having trouble understanding exactly how it should be done and in particular, how to manage the forest of trees. After reading the Wikipedia description of Disjoint Sets…
Isaac
  • 201
  • 1
  • 2
  • 3
20
votes
2 answers

Union/find algorithm without union by rank for disjoint-set forests data structure

Here's a breakdown on the union/find algorithm for disjoint set forests on wikipedia: Barebone disjoint-set forests... (O(n)) ... with union by rank ... (now improved to O(log(n)) ... with path compression (now improved to O(a(n)), effectively…
polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
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
12
votes
2 answers

Disjoint set implementation in Python

I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows: class DisjointSet: def __init__(self, vertices, parent): self.vertices = vertices self.parent = parent def find(self, item): …
Abrar
  • 6,874
  • 9
  • 28
  • 41
12
votes
5 answers

c++ test if 2 sets are disjoint

I know the STL has set_difference, but I need to just know if 2 sets are disjoint. I've profiled my code and this is slowing my app down quite a bit. Is there an easy way to see if 2 sets are disjoint, or do I need to just roll my own code? EDIT: I…
rlbond
  • 65,341
  • 56
  • 178
  • 228
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
9
votes
2 answers

Disjoint sets on apache spark

I trying to find algorithm of searching disjoint sets (connected components/union-find) on large amount of data with apache spark. Problem is amount of data. Even Raw representation of graph vertex doesn't fit in to ram on single machine. Edges also…
Puh
  • 305
  • 1
  • 10
9
votes
2 answers

Is there an example to make Union & find algorithm without union by rank run in Omega(q log n)?

Recently, I read this and was surprised that the time complexity of the union & find algorithm just with the path compression was O((m+n) log n), where m is the number of 'find' queries and n is the number of 'merge' queries. I was interested in…
Love Paper
  • 471
  • 1
  • 4
  • 15
9
votes
2 answers

How to code the maximum set packing algorithm?

Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint . The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise…
user3080029
  • 553
  • 1
  • 8
  • 19
8
votes
5 answers

Testing for a circuit when implementing Kruskalls algorithm

I'm trying to write a program that would find the minimum spanning tree. But one problem I am having with this algorithm, is testing for a circuit. What would be the best way to do this in java. Ok here is my code import java.io.*; import…
Steffan Harris
  • 9,106
  • 30
  • 75
  • 101
8
votes
1 answer

Application of Union+Find algorithm(Disjoint Set)

Problem Statement: Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return…
user1008636
  • 2,989
  • 11
  • 31
  • 45
7
votes
4 answers

How to use Disjoint Sets in Connected Component labeling?

I am having some hard time using Disjoint Sets in Connected Component Labeling. I have looked on many examples and also on this question where Bo Tian provided a very good implementation of Disjoint Sets as C++ linked list. I have already…
Patryk
  • 22,602
  • 44
  • 128
  • 244
7
votes
2 answers

Implementing equivalence relations in C++ (using boost::disjoint_sets)

Assume you have many elements, and you need to keep track of the equivalence relations between them. If element A is equivalent to element B, it is equivalent to all the other elements B is equivalent to. I am looking for an efficient data…
D R
  • 21,936
  • 38
  • 112
  • 149
7
votes
1 answer

Printing out nodes in a disjoint-set data structure in linear time

I'm trying to do this exercise in Introduction to Algorithms by Cormen et al that has to do with the Disjoin Set data structure: Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's…
user1596241
1
2 3
…
12 13