பிரிந்த-சेட் (union-find) கட்டமைப்பு என்றால் என்ன, பாதை சுகுமாரம் மற்றும் தரம் மூலம் ஒன்றிணைப்பு உடன்?

Question

Accepted Answer

**பிரிந்த-சேட்** (union-find) வேறுவேறு குழுக்களாக பிரிந்த உপাதानங்களைக் கண்காணிக்கிறது மற்றும் "**இவ்விரு வைகளும் ஒரே குழுவில் உள்ளனவா?**" மற்றும் "**இரண்டு குழுக்களை ஒன்றிணையுங்கள்**" என்பதற்கு **கிட்டத்தட்ட மாறாத நேரத்தில்** பதிலளிக்கிறது. **பாதை சுகுமாரம்** மற்றும் **தரம் மூலம் ஒன்றிணைப்பு** உடன், இரண்டு செயல்பாடுகளும் **O(α(n))** இல் இயங்குகின்றன — பயனுள்ள O(1) (α என்பது தலைகீழ் Ackermann செயல்பாடு)।

## இது எப்படி வேலை செய்கிறது

ஒவ்வொரு சேட்டும் ஒரு மரம்; **மூல** சேட்டின் பிரতிநிதி. `find` மூலம் நடக்கிறது; `union` ஒரு மூலை மற்றொன்றின் கீழ் இணைக்கிறது।

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## குறியீடு

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| செயல்பாடு | நேரம் (இரண்டு மேம்பাடுகளுடன்) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## பொதுவான உபயோகங்கள்

- **Kruskal இன் MST** — சுழற்சிகள் இல்லாமல் கூறுகளை ஒன்றிணையுங்கள்.
- **இணைக்கப்பட்ட கூறுகள்** ஒரு கிராபு அல்லது கட்டத்தில்.
- **இயக்க সংযோजकता** மற்றும் நெட்வொர்க்/பெரிகோலேசன் சிக்கல்கள்।

## ஏன் இது முக்கியம்

Union-find குழு மற்றும் சংযோजக சிக்கல்களை தீர்க்கிறது, அவை வேறுவேறு O(n) கிராப் பயணங்களை தேவை செய்யும், அவற்றை கிட்டத்தட்ட O(1) க்கு வினாத்திற்கு சுருக்குகிறது।

சேட்டுகளை படிப்படியாக ஒன்றிணையுங்கள் மற்றும் சংயோजகதையை சோதிக்க வேண்டிய போது இது ஒரு கோ-டு கருவி — பெரியவர் மட்ட சேம்புளா கேள்வி।