"""Disjoint Set Union (Union-Find) — চালানো যায় এমন reference implementation. ভেতরে কী আছে (উপর থেকে নিচে পড়ো): 1. DSU class -- path compression (halving) + union by size 2. Cycle detection demo -- প্রথম যে union() False দেয়, সে-ই একটা cycle বন্ধ করে 3. Component counting -- edges stream হতে হতে group count নামতে দেখা 4. Grouping demo -- find() দিয়ে items-কে তাদের final group-এ bucket করা আমাকে চালাও: python implementation.py প্রতিটা demo তার result assert করে, তাই চুপচাপ শেষ হওয়া মানে সব ঠিক আছে। শুধু standard library। """ # --------------------------------------------------------------------------- # 1. DSU class # --------------------------------------------------------------------------- # Mental model: এক array-র ভেতরে বাস করা trees-এর একটা forest। # parent[x] = x যাকে point করে; যে node নিজেকেই point করে সে একটা ROOT, # তার পুরো group-এর "spokesperson" (representative)। # # দুটো বিখ্যাত optimization, দুটোই এখানে আছে: # - path compression (halving form): find যে trees-এ হাঁটে, সেগুলোকে flatten করে # - union by size: ছোট tree সবসময় বড় root-এর নিচে ঝোলে # দুটো মিলে: প্রতি operation-এ amortized O(alpha(n)), যেখানে alpha হলো inverse # Ackermann function — এই universe-এ আঁটে এমন যেকোনো input-এর জন্য বড়জোর 4। # অনুবাদ: প্রতিটা operation-কে constant time ধরো। class DSU: def __init__(self, n): """n-টা singleton group বানাও: 0..n-1, প্রত্যেকে নিজের নিজের root।""" self.parent = list(range(n)) # সবাই নিজেকেই point করে self.size = [1] * n # প্রতিটা tree শুরু হয় 1 node দিয়ে self.components = n # আলাদা group-এর live count def find(self, x): """x-এর group-এর representative (root) return করো। Iterative "path halving": উপরে হাঁটার সময়, পথে পড়া প্রতিটা node-কে তার GRANDPARENT-এ point করাও। এক pass, কোনো recursion-limit-এর চিন্তা নেই, আর chains প্রতিবার হাঁটলে অর্ধেক হয়ে যায়। """ while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # এক generation skip করো x = self.parent[x] return x def union(self, x, y): """x আর y-এর group merge করো। সত্যিকারের merge হলে True return করে, আর তারা যদি ALREADY একই group-এ থাকে তাহলে False। ওই boolean-টাই গোপন অস্ত্র: একটা undirected graph-এর edges-গুলোকে union()-এ খাওয়ালে, প্রথম False-টাই ঠিক সেই edge যেটা একটা cycle বন্ধ করে। """ rx, ry = self.find(x), self.find(y) if rx == ry: return False # একই spokesperson: কিছু করার নেই # Union by size: ছোট tree বড় root-এর নিচে ঝোলে, তাই কম সংখ্যক node # "এক step গভীরে" যাওয়ার খরচ দেয়। Trees অগভীর থাকে। if self.size[rx] < self.size[ry]: rx, ry = ry, rx # নিশ্চিত করো rx-ই বড় root self.parent[ry] = rx # একটামাত্র pointer write group দুটো merge করে self.size[rx] += self.size[ry] self.components -= 1 # প্রতিটা সত্যিকারের merge একটা group সরায় return True def connected(self, x, y): """একই group? representatives-এর একটা comparison।""" return self.find(x) == self.find(y) def group_size(self, x): """x-এর group-এ কতগুলো element আছে? (Sizes শুধু roots-এই valid।)""" return self.size[self.find(x)] # --------------------------------------------------------------------------- # 2. Undirected graph-এ cycle detection # --------------------------------------------------------------------------- # Fact: দুটো ALREADY-connected node-এর মধ্যে একটা edge যোগ করলে একটা cycle বন্ধ হয়। # union() False return করা ঠিক সেটাই detect করে। কোনো DFS coloring লাগে না। def first_cycle_edge(n, edges): """প্রথম যে edge একটা cycle বন্ধ করে সেটা return করো, আর graph যদি পুরোটা জুড়ে একটা forest (cycle-free) থেকে যায় তাহলে None।""" dsu = DSU(n) for u, v in edges: if not dsu.union(u, v): # u, v already connected... return (u, v) # ...তাই এই edge একটা loop সম্পূর্ণ করে return None # --------------------------------------------------------------------------- # 3. Streaming edges দিয়ে component counting # --------------------------------------------------------------------------- def count_components(n, edges): """সব edges যোগ করার পরে connected group-এর সংখ্যা। DFS components যে উত্তর দিত সেটাই (../09-graphs/), কিন্তু edges stream হতে হতে DSU count-টা LIVE রাখে — প্রতি query-তে নতুন করে traverse করতে হয় না। """ dsu = DSU(n) for u, v in edges: dsu.union(u, v) return dsu.components # --------------------------------------------------------------------------- # 4. Grouping: elements-কে তাদের final representative দিয়ে bucket করা # --------------------------------------------------------------------------- def groups_of(dsu, n): """{representative: members-এর sorted list} return করো — আসল circles-গুলো।""" buckets = {} for x in range(n): buckets.setdefault(dsu.find(x), []).append(x) return buckets # --------------------------------------------------------------------------- # Demos — concept.md-র party, পুরোটা যাচাই করা # --------------------------------------------------------------------------- if __name__ == "__main__": # --- একটা DSU-র basic জীবন: friend-circle party (6 জন) -------------- dsu = DSU(6) assert dsu.components == 6 assert not dsu.connected(0, 1) assert dsu.union(0, 1) is True # Alice-এর সাথে Bob-এর দেখা assert dsu.union(2, 3) is True # Carol-এর সাথে Dave-এর দেখা assert dsu.union(1, 3) is True # Bob-এর সাথে Carol-এর দেখা -> circles merge assert dsu.union(0, 2) is False # already together: no-op, False দেয় assert dsu.connected(0, 3) # Alice আর Dave: এখন একই circle assert not dsu.connected(0, 4) # person 4 এখনো একা দাঁড়িয়ে assert dsu.components == 3 # {0,1,2,3}, {4}, {5} assert dsu.group_size(3) == 4 print("DSU basics ......... ok (components:", dsu.components, " size of 3's group:", dsu.group_size(3), ")") # --- Membership rule: find(x) == find(y) iff একই group --------------- assert dsu.find(0) == dsu.find(1) == dsu.find(2) == dsu.find(3) assert dsu.find(4) != dsu.find(0) print("representatives .... ok (one spokesperson for {0,1,2,3})") # --- Cycle detection --------------------------------------------------- # # 0 --- 1 edges order মেনে আসে; triangle-এর closing # | / edge (2,0)-ই প্রথম যেটা এমন দুটো node connect করে # | / যারা ALREADY একই group-এ ছিল। # 2 --- 3 # tri_edges = [(0, 1), (1, 2), (2, 0), (2, 3)] assert first_cycle_edge(4, tri_edges) == (2, 0) # একটা tree (n-1 edges, cycle নেই) অবশ্যই None report করবে: tree_edges = [(0, 1), (1, 2), (2, 3)] assert first_cycle_edge(4, tree_edges) is None print("cycle detection .... ok (triangle's closing edge: (2, 0))") # --- Component counting ------------------------------------------------- # # 0-1-2 3-4 5 -> 3 groups # assert count_components(6, [(0, 1), (1, 2), (3, 4)]) == 3 assert count_components(5, []) == 5 # edge নেই: সবাই singleton assert count_components(4, [(0, 1), (1, 2), (2, 3), (3, 0)]) == 1 print("component count .... ok (3 groups in the 6-node example)") # 'Building Roads' insight: সব কিছু connect করতে যত নতুন road লাগে # তা সমান components - 1 (প্রতিটা নতুন road ঠিক দুটো group merge করতে পারে)। roads_needed = count_components(6, [(0, 1), (1, 2), (3, 4)]) - 1 assert roads_needed == 2 print("roads needed ....... ok (components - 1 =", roads_needed, ")") # --- Grouping: আসল circles-গুলো ফিরে পাওয়া ----------------------------- party = DSU(7) for u, v in [(0, 1), (2, 3), (3, 4), (5, 6)]: party.union(u, v) circles = sorted(groups_of(party, 7).values()) assert circles == [[0, 1], [2, 3, 4], [5, 6]] print("grouping ........... ok (circles:", circles, ")") # --- Path compression, সরাসরি চোখে দেখা -------------------------------- # হাতে chain 0 <- 1 <- 2 <- 3 <- 4 বানাও, তারপর path halving সহ একটা find() # সেটাকে ছোট করতে দেখো। chain = DSU(5) chain.parent = [0, 0, 1, 2, 3] # হাতে বানানো একটা worst-case chain chain.size = [5, 1, 1, 1, 1] # (sizes এক group-এর সাথে consistent) chain.components = 1 assert chain.parent[4] == 3 # 4 root থেকে দুই-প্লাস hop দূরে শুরু করে assert chain.find(4) == 0 # root পর্যন্ত হাঁটো... assert chain.parent[4] != 3 # ...আর 4 পথেই re-point হয়ে গেছে assert chain.find(4) == 0 # উত্তর এখনো ঠিক, এখন আরো fast print("path compression ... ok (chain flattened by a single find)") print("\nAll DSU demos passed.")