Stack Overflow
Stack Overflow

Questions tagged [disjoint-union]

55 questions
22
votes
1 answer

Disjoint Union in LINQ

I have two sets (ILists) where I need all the items from the 1st list, where the item is not in the second list. Can anyone point me to the best way of achieving this with a LINQ statement?
Chris S
  • 64,770
  • 52
  • 221
  • 239
11
votes
6 answers

mysql SELECT NOT IN () -- disjoint set?

I'm having a problem getting a query to work, which I think should work. It's in the form SELECT DISTINCT a, b, c FROM t1 WHERE NOT IN ( SELECT DISTINCT a,b,c FROM t2 ) AS alias But mysql chokes where "IN (" starts. Does mysql support this syntax?…
user151841
  • 17,377
  • 29
  • 109
  • 171
6
votes
2 answers

Find the number of disjoint sets

For those not familiar with Disjoint-set data structure. https://en.wikipedia.org/wiki/Disjoint-set_data_structure I'm trying to find the no. of groups of friends from the given sets of friends and their relationships. Of course, there is no doubt…
nitte93
  • 1,820
  • 3
  • 26
  • 42
5
votes
5 answers

Disjoint-set forests - why should the rank be increased by one when the find of two nodes are of same rank?

I am implementing the disjoint-set datastructure to do union find. I came across the following statement in Wikipedia: ... whenever two trees of the same rank r are united, the rank of the result is r+1. Why should the rank of the joined tree be…
jeffreyveon
  • 13,400
  • 18
  • 79
  • 129
4
votes
2 answers

O(1) Make, Find, Union in Disjoint Sets Data Structure

Today, I had discussion with someone about Kruskal Minimum Spanning Tree algorithm because of page 13 of this slide. The author of the presentation said that if we implement disjoint sets using (doubly) linked list, the performance for Make and…
monn
  • 717
  • 1
  • 5
  • 13
4
votes
1 answer

Are constructors disjoint in Agda? (or how to disprove inj₁ x ≡ inj₂ y)

I need one more lemma showing that inj₁ x ≡ inj₂ y is absurd as part of a larger theorem about disjoint union types (⊎) in Agda. This result would follow directly from the two constructors for ⊎, namely inj₁ and inj₂, being disjoint. Is that the…
curiousleo
  • 296
  • 1
  • 7
3
votes
1 answer

My C++ function gives unusual error, regarding declaration

#include using namespace std; void union(int x, int y, int link[], int size[]) { int a = find(x, link); int b = find(y, link); if (size[a] < size[b]) swap(a,b); if ( a != b) { size[a] += size[b]; …
Anant
  • 302
  • 2
  • 11
3
votes
2 answers

Disjoint Union in C# Lists

I have two lists and I want to get the list which is the disjoint union of two lists. That is, all the items in either list that are not in both of them. This post has almost the same query as mine, except they mean something slightly different by…
Charles Taylor
  • 686
  • 6
  • 23
3
votes
1 answer

Disjoint set with Union by Size and Path Compression; possible for taller tree to become subtree of shorter tree?

Hi this is my first time posting here, I have been trying to work out a question for studying but haven't been able to figure it out: We consider the forest implementation of the disjoint-set abstract data type, with Weighted Union by size and Path…
FluffyBeing
  • 448
  • 1
  • 11
  • 27
3
votes
2 answers

Efficient search for not empty intersection (Java)

I have a method that returns an integer value or integer range (initial..final) and I want to know if values are all disjoint. Is there a more efficient solution than the following one: ArrayList list = new ArrayList(); // For…
Tommaso DS
  • 211
  • 2
  • 14
2
votes
1 answer

How to merge sets in better then O(len(set))?

I have a list of sets called groups. groups[i] is a set of labels (integers) that are part of the same group as i. For example, # idx: 0 1 2 3 4 5 6 7 groups = [{0}, {1}, {2,5,6}, {3}, {4,7}, {2,5,6}, {2,5,6},…
joseville
  • 685
  • 3
  • 16
2
votes
1 answer

Distance to representative in Disjoint set union data structure

From cp-algorithms website: Sometimes in specific applications of the DSU you need to maintain the distance between a vertex and the representative of its set (i.e. the path length in the tree from the current node to the root of the tree). and…
manu
  • 25
  • 4
2
votes
1 answer

Maximum edge weight from one node A to node B

Given a connected undirected graph having N nodes (1 <= N <= 2 * 10^5) and N-1 edges. Let's define a function F(a,b), where F(a, b) is equal to the maximum edge weight in the path from a to b. How do we find the sum of the F(a, b) for all a, b such…
Deepak Chaudhary
  • 93
  • 1
  • 8
2
votes
1 answer

how to calculate height of disjoint trees implemented with union by rank heuristic?

Since very long i am trying to solve a question from a quiz , but i am getting wrong answer , the question is as follows :- Consider the program: for i from 1 to 12: MakeSet(i) Union(2, 10) Union(7, 5) Union(6, 1) Union(3, 4) Union(5, 11) Union(7,…
Ajay
  • 49
  • 2
  • 4
2
votes
1 answer

Scala variable parameter count Either

Is there implemented variable parameter count scala Either in some library, I mean something analogic to HList. I don't want to implement it by myself :-)
ryskajakub
  • 6,351
  • 8
  • 45
  • 75
1
2 3 4