001 — Find if Path Exists in Graph¶

Source¶

Original source: Classic dynamic-connectivity exercise
Platform: LeetCode — https://leetcode.com/problems/find-if-path-exists-in-graph/
Topic: disjoint set union
Difficulty: Easy
Pattern: dynamic connectivity (same group?)
Basic idea inherited from: ../../09-graphs/-এর একই problem-এর BFS version; এখানে আমরা path খুঁজি না, শুধু "একই component কিনা" জিজ্ঞেস করি

1. Problem in simple words¶

n টা node (0 থেকে n−1) আর কতগুলো undirected edge দেওয়া আছে। তোমাকে বলতে হবে — source থেকে destination-এ যাওয়ার কোনো path আছে কি না। শুধু হ্যাঁ/না; আসল রাস্তাটা কেমন তা জানতে চাওয়া হয়নি।

n = 6
edges = (0-1) (0-2) (3-5) (5-4) (4-3)
source = 0, destination = 5  ->  path নেই?  না!  (False)
source = 0, destination = 2  ->  path আছে?  হ্যাঁ! (True)

2. Which basic idea does this inherit from?¶

মূল ভিত হলো "দুটো node কি একই connected component-এ?" — এটাই DSU-র জন্মগত প্রশ্ন। ../../09-graphs/-এ তুমি এই same problem BFS দিয়ে solve করেছ: source থেকে হেঁটে দেখেছ destination ছোঁয়া যায় কি না। DSU সেই হাঁটাটা বাদ দিয়ে শুধু representative মেলায়।

3. What is the hidden math or logic?¶

লুকানো logic একটা equivalence relation: "connected" সম্পর্কটা reflexive (নিজে নিজের সাথে যুক্ত), symmetric (undirected), আর transitive (a–b আর b–c যুক্ত হলে a–c যুক্ত)। এমন relation মানেই node-গুলো ভাগ হয়ে যায় কতগুলো disjoint equivalence class-এ — যেগুলোই connected components। দুটো node একই class-এ থাকলেই path আছে।

4. Which data structure is needed?¶

একটা Disjoint Set Union (union–find) — দুটো integer array: parent (কে কাকে point করে) আর size (প্রতি group কত বড়)। কোনো adjacency list রাখার দরকারই নেই; edge গুলো শুধু union করার কাঁচামাল।

5. Why this data structure fits¶

প্রশ্নটা path নয়, শুধু membership — "same group?"। DSU ঠিক এই দুটো কাজই near-constant time-এ করে: union দিয়ে দুই group জোড়া, find দিয়ে representative বের করা। Path বা distance DSU মনে রাখে না, কিন্তু এখানে সেসব লাগেও না — তাই এটাই সবচেয়ে হালকা fit।

6. Real-life analogy¶

ভাবো একটা বিশাল party, যেখানে friend circle গুলো পরিচয় হতে হতে মিশে যাচ্ছে (concept.md-র সেই party)। তুমি জানতে চাও — "Alice আর Frank কি একই circle-এ?" তুমি পুরো ঘর খুঁজে বেড়াও না; দুজনকেই জিজ্ঞেস করো "তোমার circle-এর spokesperson কে?" একই spokesperson হলে একই circle। Spokesperson = representative।

7. Visual explanation¶

প্রতিটা edge-কে union হিসেবে খাওয়াও; forest গড়ে ওঠে। তারপর দুটো find মেলাও।

edges: (0-1) (0-2) (3-5) (5-4)

শুরু:   *0  *1  *2  *3  *4  *5     parent: [0,1,2,3,4,5]

union(0,1):     *0   *2  *3  *4  *5
                 |
                 1                  parent: [0,0,2,3,4,5]

union(0,2):     *0      *3  *4  *5
               /  \
              1    2                parent: [0,0,0,3,4,5]

union(3,5):     *0      *3   *4
               / \       |
              1   2      5          parent: [0,0,0,3,4,3]

union(5,4):     *0       *3
               / \      /  \
              1   2    5    4       parent: [0,0,0,3,4,3]  (4 hangs under 3)

প্রশ্ন: path(0, 5)?  find(0)=0,  find(5)=3   ->  0 != 3  ->  False
প্রশ্ন: path(0, 2)?  find(0)=0,  find(2)=0   ->  0 == 0  ->  True

8. Example input and output¶

Input : n=3, edges=[[0,1],[1,2],[2,0]], source=0, destination=2
Output: True

Input : n=6, edges=[[0,1],[0,2],[3,5],[5,4],[4,3]], source=0, destination=5
Output: False

Edge case (একই node): n=1, edges=[], source=0, destination=0  ->  True

9. Brute force thinking¶

সরল চিন্তা: adjacency list বানাও, তারপর source থেকে BFS বা DFS চালাও; destination ছুঁলে True, queue/stack ফুরিয়ে গেলে False।

1) প্রতিটা edge -> adjacency list-এ যোগ করো
2) source থেকে BFS শুরু করো
3) destination পেলে থামো -> True; না পেলে -> False

10. Why brute force is slow¶

একটা মাত্র query-র জন্য BFS ঠিকঠাক — O(V + E)। কিন্তু যদি অনেক (source, destination) query আসত, অথবা edge গুলো একটা একটা করে আসত আর মাঝে মাঝে query ঢুকত (dynamic connectivity), তখন প্রতিবার পুরো graph নতুন করে চষা অপচয়। BFS query-র মাঝে কিছু মনে রাখে না; DSU মনে রাখে।

11. Key observation¶

মূল observation: আসল রাস্তাটা অপ্রাসঙ্গিক। আমাদের শুধু জানা দরকার দুটো node একই group-এ কি না। তাই edge-গুলোকে relation হিসেবে গুঁড়িয়ে disjoint set-এ ভেঙে ফেলো; query হয়ে যায় দুটো find-এর তুলনা।

12. Optimized intuition¶

সব edge union করে component গড়ে নাও — এটা একবারের কাজ। তারপর find(source) == find(destination) দিয়ে উত্তর দাও। Path compression + union by size থাকায় প্রতিটা operation amortized প্রায় constant — এত fast যে interview-তে α(n)-কে নির্দ্বিধায় "≈ O(1)" ধরতে পারো।

13. Thinking tweak¶

মোচড়: "source থেকে destination-এ কীভাবে পৌঁছব?" — এই হাঁটার চিন্তাটা ছেড়ে দাও। বদলে জিজ্ঞেস করো "ওরা কি একই দলের?" পথের প্রশ্নকে দলের প্রশ্নে অনুবাদ করলেই DSU দরজা খুলে দেয়।

14. Step-by-step dry run¶

Input n=6, edges=[[0,1],[0,2],[3,5],[5,4]], source=0, destination=5:

union(0,1) → roots 0,1 আলাদা; parent[1]=0, size[0]=2 → component {0,1}
union(0,2) → find(0)=0, find(2)=2; parent[2]=0, size[0]=3 → {0,1,2}
union(3,5) → parent[5]=3, size[3]=2 → {3,5}
union(5,4) → find(5)=3, find(4)=4; size[3]=2>1, parent[4]=3 → {3,5,4}
query: find(0)=0, find(5)=3 → 0 != 3 → False

15. Python solution¶

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                 # আগে থেকেই এক group
        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 valid_path(n, edges, source, destination):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)                 # সব edge দিয়ে component গড়ো
    return dsu.find(source) == dsu.find(destination)


# ---- tests ----
assert valid_path(3, [[0, 1], [1, 2], [2, 0]], 0, 2) is True
assert valid_path(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5) is False
assert valid_path(1, [], 0, 0) is True          # একই node
assert valid_path(2, [], 0, 1) is False         # কোনো edge নেই
print("সব test pass!")

16. Line-by-line code explanation¶

parent = list(range(n)) — শুরুতে প্রত্যেকে নিজের root, মানে n টা আলাদা group।
find — root-এ ওঠার পথে প্রতিটা node-কে grandparent-এ re-point করে (path halving), তাই পরের বার হাঁটা ছোট।
union — দুই root আলাদা হলে ছোট tree-টা বড়টার নিচে ঝোলায়; সমান হলে আগে থেকেই এক group, False ফেরায়।
for u, v in edges: dsu.union(u, v) — সব connection গিলে component তৈরি।
return dsu.find(source) == dsu.find(destination) — একই representative মানেই path আছে।

17. Output walkthrough¶

প্রথম test-এ triangle 0-1-2 এক component, তাই path(0,2) True। দ্বিতীয়টায় {0,1,2} আর {3,4,5} দুটো আলাদা দ্বীপ, তাই path(0,5) False। তৃতীয়টায় source==destination, find একই — True। চতুর্থটায় edge নেই, 0 আর 1 আলাদা — False। শেষে print: সব test pass!।

18. Time complexity¶

O((V + E) · α(V)) ≈ O(V + E) — প্রতিটা edge একটা union, query দুটো find; প্রতিটা operation amortized near-constant (inverse Ackermann, যা বাস্তবে ≤ 4)।

19. Space complexity¶

O(V) — শুধু parent আর size array; adjacency list রাখাই লাগে না।

20. Common mistakes¶

find(source) == find(destination)-এর বদলে parent[source] == parent[destination] compare করা — tree flat না হলে parent ≠ representative; এটাই classic DSU bug।
DSU array-র size n-এর বদলে edge-সংখ্যা দিয়ে নেওয়া।
source == destination edge case ভুলে যাওয়া (এখানে এমনিতেই True আসে, কারণ একই index-এর find একই)।

21. Which basic problem this inherits from¶

ভিত্তি: ../../09-graphs/-এর connectivity / "path exists" BFS। ওখানে তুমি queue দিয়ে হেঁটেছিলে; এখানে union/find দিয়ে group মিলিয়েছ। একটামাত্র static query-তে দুটোই O(V+E); কিন্তু query স্রোতের মতো এলে DSU এগিয়ে। DSU-র মূল snippet ../concept.md-র "বারো লাইন"-এ আছে।

22. Similar harder problems¶

Number of Provinces (component গোনা) — https://leetcode.com/problems/number-of-provinces/ (এই tracker-এর #2)
Graph Valid Tree (connectivity + cycle) — https://leetcode.com/problems/graph-valid-tree/ (#4)
Number of Islands II (streaming connectivity — যেটা traversal ভালো পারে না) — https://leetcode.com/problems/number-of-islands-ii/ (#13)

23. Pattern learned¶

Dynamic connectivity: edge-গুলো union-এ খাইয়ে component গড়ো, তারপর "same group?" প্রতিটা query-তে দুই find-এর তুলনায় উত্তর দাও। Path/distance যেখানে লাগে না, সেখানে DSU সবচেয়ে হালকা ও দ্রুত উত্তর।

24. Final summary¶

ভবিষ্যতের আমাকে: "path exists?" দেখলে আগে ভাবো — আসল রাস্তা লাগবে, নাকি শুধু same-group? শুধু same-group হলে BFS ভুলে DSU ধরো: সব edge union করো, দুটো find মেলাও, শেষ। এটাই dynamic-connectivity-র সবচেয়ে পরিষ্কার রূপ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।