001 — Find if Path Exists in Graph¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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 কিনা" জিজ্ঞেস করি

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

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)

Input ও 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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

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

ভেতরের যুক্তি¶

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

কী দিয়ে তথ্য রাখব¶

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

এটি কেন উপযুক্ত¶

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

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে¶

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

যে বিষয়টি খেয়াল করতে হবে¶

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

আরও কম কাজে সমাধান¶

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

ভাবনার পরিবর্তন¶

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

ছবিতে বোঝা¶

প্রতিটা 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

ছোট input-এ ধাপে ধাপে¶

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

কোড ও ব্যাখ্যা¶

Python¶

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                 # আগে থেকেই এক 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!")

কোডের প্রতিটি অংশ¶

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 আছে।

Output মিলিয়ে দেখা¶

প্রথম 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!।

খরচ ও সাধারণ ভুল¶

সময়¶

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

অতিরিক্ত জায়গা¶

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

যে ভুলগুলো এড়াতে হবে¶

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 একই)।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

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

পরের অনুশীলন¶

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)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "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।