Problem link ও উৎস
- **Original source:** Classic equivalence-class exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** equivalence classes
- **Basic idea inherited from:** `10`-এর grouping pattern; `==` দিয়ে variable union করো, তারপর `!=` গুলো ভাঙছে কি না দেখো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো equation দেওয়া, প্রতিটা চার অক্ষরের string — হয় `"a==b"` (সমান) নয় `"a!=b"` (অসমান), যেখানে দুই পাশে একটা করে lowercase variable। তোমাকে বলতে হবে — সব variable-এ এমন মান বসানো সম্ভব কি না যাতে **প্রতিটা** equation সত্যি হয়।
```text
equations = ["a==b", "b!=a"]
a==b বলে a আর b সমান হতেই হবে; কিন্তু b!=a বলে আবার ভিন্ন
একসাথে অসম্ভব -> False
```
### Input ও output {#8-example-input-and-output}
```text
Input : ["a==b","b!=a"]
Output: False
Input : ["b==a","a==b"]
Output: True
Input : ["a==b","b==c","a==c"]
Output: True
Input : ["a==b","b!=c","c==a"]
Output: False (a==b আর c==a -> a,b,c এক class; কিন্তু b!=c চায় ভিন্ন)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
party-র friend circle, তবে variable-রা মানুষ। `==` মানে "এই দুজন আসলে একই পরিচয়" — তাদের circle মেশাও। সব মেশানো শেষে কয়েকটা circle টিকে থাকে। এবার `!=` মানে "এই দুজন অবশ্যই ভিন্ন মানুষ" — যদি দেখা যায় তারা **একই** circle-এ, তাহলে বিরোধ: একই লোককে দুজন ভিন্ন মানুষ বলা যায় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো এই tracker-এর **grouping pattern (Pattern D)** — DSU আসলে একটা **equivalence-relation engine**। `==` সম্পর্কটা reflexive, symmetric, transitive — তাই এটা variable-গুলোকে কতগুলো **equivalence class**-এ ভাগ করে। প্রথমে সব `==` দিয়ে union করে class বানাও; তারপর প্রতিটা `!=` যাচাই করো — দুই পাশ একই class-এ পড়লে contradiction।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **equivalence relation**: `==` reflexive (`a==a`), symmetric (`a==b` ⇒ `b==a`), আর transitive (`a==b` ও `b==c` ⇒ `a==c`)। এমন relation variable-দের disjoint class-এ ভাগ করে — প্রতিটা class-এর সবাই একই মান পাবে। `!=` constraint বলছে দুটো variable ভিন্ন class-এ থাকতে হবে। তাই: সব `==` মিশিয়ে class গড়ো, তারপর কোনো `!=` যেন এক class-কে নিজের সাথে ভিন্ন হতে না বলে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** ঠিক **26** element-এর (`'a'` থেকে `'z'`)। variable গুলো এক অক্ষর, তাই `ord(ch) - 97` দিয়ে 0–25 index। `==` গুলো union, `!=` গুলো find-তুলনা।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা বিশুদ্ধ "কোন variable কোন দলে?" — equivalence class। DSU merge-only দুনিয়ায় ঠিক এই কাজ: `==` দিয়ে দল মেশাও, `!=` দিয়ে দুই দল আলাদা থাকা যাচাই করো। মাত্র 26 element, কোনো path/distance লাগে না — তাই DSU সবচেয়ে পরিষ্কার fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: variable গুলোকে graph-এর node ভাবো, `==` গুলোকে edge। প্রতিটা variable-এর জন্য DFS/BFS দিয়ে connected component বের করো (কে কার সাথে সমান)। তারপর প্রতিটা `!=` দেখো — দুই পাশ যদি একই component-এ থাকে, contradiction।
```text
1) == edge দিয়ে adjacency list বানাও
2) DFS দিয়ে প্রতিটা variable-এর component-id বের করো
3) প্রতি !=: দুই পাশের component-id সমান হলে -> False
4) সব != টিকলে -> True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
মাত্র 26 variable বলে DFS-ও কার্যত fast — কিন্তু এতে adjacency গড়া, recursion, আর component-id label করা লাগে। DSU দুই-পাস-এ (`==` union, তারপর `!=` find) একই কাজ করে কোনো adjacency বা recursion ছাড়াই, আর "same class?" প্রশ্নটা ঠিক DSU-র জন্মগত operation। তাই DSU সরল ও স্বাভাবিক।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **order matters — আগে সব `==`, পরে সব `!=`।** তুমি প্রথমে পুরো equality-graph গড়ে নাও (সব class স্থির হয়), তারপরই `!=`-গুলো যাচাই করো। মিশিয়ে process করলে এমন `!=` পরে আসা `==` দিয়ে ভেঙে যেতে পারে — তাই দুটো আলাদা phase জরুরি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
26-element DSU নাও। **Phase 1:** সব equation-এ যেগুলো `==`, দুই পাশ union করো। **Phase 2:** সব `!=` equation-এ দুই পাশের `find` মেলাও — সমান হলে সাথে সাথে `False`। কোনো `!=` না ভাঙলে `True`। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(E)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "equation-গুলো একে একে পড়ে সাথে সাথে যাচাই করি" — এই single-pass চিন্তা ছাড়ো। বদলে ভাবো "আগে সব 'সমান' মিশিয়ে দল পাকা করি, তারপর কোনো 'অসমান' সেই দল ভাঙছে কি না দেখি।" Equality আর inequality-কে দুই আলাদা phase-এ ভাগ করাই চাবি।
### ছবিতে বোঝা {#7-visual-explanation}
আগে সব `==` union; তারপর প্রতি `!=`-এ দুই পাশের find মেলাও — সমান হলে False।
```text
equations = ["a==b", "b==c", "a!=c"] (a=0, b=1, c=2)
Phase 1 — সব == union:
শুরু: *a *b *c parent: [a,b,c]
এই input-এ শুধু a,b,c দেখানো; বাকি 23টি letter singleton থেকে যায় এবং ব্যবহৃত হয় না।
a==b -> union(0,1): *a *c
|
b {a,b}
b==c -> union(1,2): find(1)=a, find(2)=c -> merge
*a
/ \
b c {a,b,c}
Phase 2 — != যাচাই:
a!=c -> find(a)=a, find(c)=a -> সমান! -> contradiction -> False
------ satisfiable case: ["a==b", "b!=c"] ------
Phase 1: union(a,b) -> {a,b}; c একা
Phase 2: b!=c -> find(b)=a, find(c)=c -> আলাদা -> ঠিক আছে -> True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["a==b","b!=c","c==a"]` (a=0, b=1, c=2):
1. **Phase 1 (==):** `a==b` → `union(0,1)` → {a,b}; `c==a` → `union(2,0)` → find(2)=2, find(0)=0, merge → {a,b,c}
2. **Phase 2 (!=):** `b!=c` → `find(1)` আর `find(2)` — দুটোই এখন এক root (0) → সমান!
3. contradiction → return **False**
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n # প্রতিটা group-এ একজন
def find(self, x): # representative + path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, x, y): # union by size; merge হলে True
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx # rx এখন বড় root
self.parent[ry] = rx # ছোটটা বড়টার নিচে ঝোলে
self.size[rx] += self.size[ry]
return True
def equations_possible(equations):
dsu = DSU(26) # 'a'..'z' -> index 0..25
for eq in equations: # Phase 1: সব == union করো
if eq[1] == '=':
dsu.union(ord(eq[0]) - 97, ord(eq[3]) - 97)
for eq in equations: # Phase 2: != গুলো যাচাই করো
if eq[1] == '!':
if dsu.find(ord(eq[0]) - 97) == dsu.find(ord(eq[3]) - 97):
return False # এক class-কে ভিন্ন বলা -> contradiction
return True
# ---- tests ----
assert equations_possible(["a==b", "b!=a"]) is False
assert equations_possible(["b==a", "a==b"]) is True
assert equations_possible(["a==b", "b==c", "a==c"]) is True
assert equations_possible(["a==b", "b!=c", "c==a"]) is False
assert equations_possible(["c==c", "b==d", "x!=z"]) is True # self-eq + আলাদা class
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dsu = DSU(26)` — variable গুলো একক lowercase অক্ষর, তাই ঠিক 26 element যথেষ্ট।
- `if eq[1] == '='` — string-এর index 1-এ operator-এর প্রথম অক্ষর; `'='` মানে এটা `==` equation।
- `dsu.union(ord(eq[0]) - 97, ord(eq[3]) - 97)` — index 0 আর 3 হলো দুই variable; `ord(ch) - 97` দিয়ে `'a'..'z'` কে 0..25-এ map।
- `if eq[1] == '!'` (দ্বিতীয় loop) — এবার শুধু `!=` equation; Phase 1 শেষ হওয়ায় সব class স্থির।
- `if dsu.find(...) == dsu.find(...): return False` — দুই পাশ একই class-এ পড়লে "ভিন্ন হও" শর্ত ভাঙে — অসম্ভব।
- `return True` — কোনো `!=` ভাঙেনি, তাই একটা valid assignment আছে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ `a==b` দুটো এক class করে; `b!=a` সেই class-কে ভিন্ন বলে — False। দ্বিতীয়টায় দুটোই `==`, কোনো `!=` নেই — True। তৃতীয়টায় a,b,c এক class, সব `==` সামঞ্জস্যপূর্ণ — True। চতুর্থটায় a,b,c এক class হয়ে যায়, কিন্তু `b!=c` চায় ভিন্ন — False। পঞ্চমটায় `c==c` ক্ষতিহীন, b,d এক class, x আর z আলাদা — True। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(E · α(1)) ≈ O(E)** — E হলো equation-সংখ্যা; দুটো pass, প্রতিটায় প্রতি equation একটা `union` বা দুটো `find`, প্রতিটা amortized near-constant। মাত্র 26 element বলে α কার্যত ধ্রুবক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — DSU array সবসময় ঠিক 26 element, input-size-নিরপেক্ষ; তাই constant extra space।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- দুই phase মিশিয়ে single pass-এ করা — তখন আগে আসা `!=` পরে আসা `==` দিয়ে ভেঙে যেতে পারে; **আগে সব `==`, পরে সব `!=`** — order জরুরি।
- string parsing-এ index ভুল — operator index 1–2, variable index 0 আর 3; `eq[2]` কে variable ভাবা একটা সহজ ভুল।
- DSU size 26-এর বদলে equation-সংখ্যা দিয়ে নেওয়া।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: এই tracker-এর grouping pattern (Pattern D, concept.md) — "reflexive + symmetric + transitive যা কিছু, তা-ই DSU-আকৃতির"। এখানে `==` ঠিক সেই equivalence relation। DFS দিয়ে component বের করেও সমাধান হয়; কিন্তু "same class?" প্রশ্নটা DSU-র `find`-এই সবচেয়ে সরাসরি, আর দুই-phase structure DSU-তে স্বাভাবিক।
### পরের অনুশীলন {#22-similar-harder-problems}
- Smallest String With Swaps (group বানিয়ে ভেতরে sort) —