Disjoint Set Union यानि DSU

Disjoint Set Union यह track रखने जैसा है कि कौन से kids किस friend group में हैं और जब वे friends बनें तो तुरंत दो groups merge करना।

In this page:

What is DSU
Find Operation
Union Operation
Path Compression
Applications

Syntax

markup

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb

What is DSU

Disjoint Set Union (Union-Find) elements के एक collection को अलग, non-overlapping groups में split track रखता है, और efficiently दो सवालों का जवाब देता है: एक element किस group से belong करता है, और क्या दो elements उसी group में हैं।

उदाहरण: What is DSU

#include <iostream>
using namespace std;
int main() {
	cout << "DSU tracks separate groups, answers 'same group?' and merges two groups efficiently";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently");
	}
}

print("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently")

#include <stdio.h>
int main() {
	printf("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently");
	return 0;
}

Find Operation

Find operation parent pointers के through एक element से ऊपर चलता है जब तक यह उस group के representative (root) तक न पहुंचे, इसलिए दो elements बिल्कुल तब उसी set में हैं जब find दोनों के लिए वही representative return करे।

उदाहरण: Find Operation

#include <iostream>
using namespace std;
int parent[5] = {0,0,1,3,3};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() { cout << "Root of element 2: " << find(2); return 0; }

public class Main {
	static int[] parent = {0,0,1,3,3};
	static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
	public static void main(String[] args) { System.out.println("Root of element 2: " + find(2)); }
}

parent = [0,0,1,3,3]
def find(x):
    return x if parent[x] == x else find(parent[x])
print("Root of element 2:", find(2))

#include <stdio.h>
int parent[5] = {0,0,1,3,3};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() { printf("Root of element 2: %d", find(2)); return 0; }

Union Operation

Union operation एक set के representative को दूसरे की ओर point कराके दो अलग sets को एक में merge करता है, effectively दो पहले अलग groups को एक single connected group में जोड़ते हुए।

उदाहरण: Union Operation

#include <iostream>
using namespace std;
int parent[5] = {0,1,2,3,4};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
void unite(int a, int b) { parent[find(a)] = find(b); }
int main() { unite(0,1); cout << "0 and 1 merged, same root now: " << (find(0)==find(1)); return 0; }

public class Main {
	static int[] parent = {0,1,2,3,4};
	static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
	static void unite(int a, int b) { parent[find(a)] = find(b); }
	public static void main(String[] args) { unite(0,1); System.out.println("0 and 1 merged, same root now: " + (find(0)==find(1))); }
}

parent = [0,1,2,3,4]
def find(x):
    return x if parent[x] == x else find(parent[x])
def unite(a, b):
    parent[find(a)] = find(b)
unite(0,1)
print("0 and 1 merged, same root now:", find(0)==find(1))

#include <stdio.h>
int parent[5] = {0,1,2,3,4};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
void unite(int a, int b) { parent[find(a)] = find(b); }
int main() { unite(0,1); printf("0 and 1 merged, same root now: %d", find(0)==find(1)); return 0; }

Path Compression

एक find operation के बाद, path compression रास्ते में visited हर node को सीधे discovered root की ओर re-point करता है, इसलिए उन nodes में से किसी पर अगला find लगभग तुरंत खत्म होता है बजाय वही लंबी chain फिर traverse करने के।

उदाहरण: Path Compression

#include <iostream>
using namespace std;
int parent[5] = {0,0,1,2,3};
int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
int main() { find(4); cout << "After find(4), node 4 points directly at root: " << parent[4]; return 0; }

public class Main {
	static int[] parent = {0,0,1,2,3};
	static int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
	public static void main(String[] args) { find(4); System.out.println("After find(4), node 4 points directly at root: " + parent[4]); }
}

parent = [0,0,1,2,3]
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
find(4)
print("After find(4), node 4 points directly at root:", parent[4])

#include <stdio.h>
int parent[5] = {0,0,1,2,3};
int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
int main() { find(4); printf("After find(4), node 4 points directly at root: %d", parent[4]); return 0; }

Applications

DSU edges को एक-एक करके जोड़े जाते समय connectivity track करने का standard tool है (क्या इस नई edge ने दो पहले अलग components जोड़े?) और Kruskal के minimum spanning tree algorithm के पीछे core building block है।

उदाहरण: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm");
	}
}

print("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm")

#include <stdio.h>
int main() {
	printf("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm");
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Fenwick Tree BIT Next Lesson → Sparse Table