Skip to content

004 — Graph Valid Tree

Source

  • Original source: Classic tree-validation exercise
  • Platform: LeetCode — https://leetcode.com/problems/graph-valid-tree/
  • Topic: disjoint set union
  • Difficulty: Medium
  • Pattern: cycle detection + component count
  • Basic idea inherited from: 10-এর "union False ফেরালে cycle" insight; এখানে দুটো শর্ত একসাথে — শূন্য cycle আর সব node এক component

1. Problem in simple words

n টা node (0 থেকে n−1) আর কতগুলো undirected edge দেওয়া। তোমাকে বলতে হবে — এই edge-গুলো মিলে একটা valid tree বানায় কি না। Tree মানে: সব node যুক্ত (একটাই component) আর কোথাও কোনো cycle নেই।

n = 5
edges = (0-1) (0-2) (0-3) (1-4)   ->  সব যুক্ত, cycle নেই  ->  True

n = 5
edges = (0-1) (1-2) (2-3) (1-3) (1-4)  ->  1-2-3-1 একটা cycle  ->  False

2. Which basic idea does this inherit from?

মূল ভিত হলো concept.md-র cycle guard — undirected graph-এ union যখন দুটো already-connected node-এ চলে, তখন সেই edge একটা cycle বন্ধ করে, আর union False ফেরায়। এই একটামাত্র insight দিয়ে cycle ধরা পড়ে। সাথে জুড়ে দাও component counting (#2), তাহলেই tree-র দুটো শর্ত হাতের মুঠোয়।

3. What is the hidden math or logic?

লুকানো logic একটা পরিষ্কার গাণিতিক fact: n-node tree-র ঠিক n−1 edge থাকে, না বেশি না কম। এর থেকে একটা সুন্দর shortcut আসে — edge-সংখ্যা ঠিক n−1 না হলে আগেই False। আর যদি ঠিক n−1 edge থাকে এবং কোনো cycle না থাকে, তাহলে graph স্বয়ংক্রিয়ভাবেই connected (n−1 edge দিয়ে cycle ছাড়া n node যোগ করার একমাত্র উপায়)। তাই দুটো check যথেষ্ট: edge গোনা + cycle না থাকা।

4. Which data structure is needed?

একটা DSU (parent + size array)। কোনো adjacency list বা recursion লাগে না — edge-গুলোকে শুধু union-এর কাঁচামাল হিসেবে খাওয়াই, আর কোনো union False ফেরায় কি না সেটা দেখি।

5. Why this data structure fits

প্রশ্নটা "tree কি না" — মানে connectivity + cycle, ঠিক DSU-র জন্মগত দুটো প্রশ্ন। union-এর return value একই সাথে merge করে আর cycle ধরিয়ে দেয়, তাই আলাদা DFS coloring বা visited bookkeeping লাগে না। Path বা distance এখানে অপ্রাসঙ্গিক, তাই DSU-ই সবচেয়ে হালকা fit।

6. Real-life analogy

party-র friend circle আবার, তবে এবার একটা নিয়ম: তুমি একটা নিখুঁত পরিচয়-শৃঙ্খল চাও যেখানে সবাই শেষমেশ এক circle-এ, কিন্তু কোনো দুজন দুবার পরিচিত হয়নি। যদি দুজন আগে-পরিচিত মানুষ আবার হাত মেলায়, সেটা একটা অপচয়ী লুপ (cycle)। আর শেষে যদি একাধিক circle টিকে থাকে, সবাই যুক্ত হয়নি। দুটোর একটাও ঘটলে — এটা "valid tree" নয়।

7. Visual explanation

প্রতিটা edge union করো; কোনো union False ফেরালে cycle ⇒ False। Loop শেষে component একটার বেশি থাকলেও False।

n = 5,  edges: (0-1) (0-2) (0-3) (1-4)   [4 edges == n-1, ভালো লক্ষণ]

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

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

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

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

union(1,4): find(1)=0, find(4)=4 -> merge
                *0
             / | | \
            1  2 3  4             parent: [0,0,0,0,0]   এক component, কোনো False -> True

------ cycle case: edges (0-1)(1-2)(2-0) ------
union(0,1) ok ; union(1,2) ok ; union(2,0): find(2)=0, find(0)=0 -> False (cycle!) -> not a tree

8. Example input and output

Input : n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
Output: True

Input : n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: False   (cycle 1-2-3-1)

Edge case (disconnected): n=4, edges=[[0,1],[2,3]]  ->  False  (দুই component)
Edge case (single node) : n=1, edges=[]             ->  True

9. Brute force thinking

সরল চিন্তা: adjacency list বানাও, একটা visited set রাখো, parent মনে রেখে DFS চালাও; DFS-এ parent ছাড়া অন্য কোনো visited node-এ গেলে cycle। শেষে visited-এর সংখ্যা n কি না দেখে connectivity যাচাই করো।

1) adjacency list বানাও
2) node 0 থেকে DFS, parent track করো
3) parent ছাড়া visited প্রতিবেশী পেলে -> cycle -> False
4) DFS শেষে visited == n না হলে -> disconnected -> False
5) দুটো check টিকলে -> True

10. Why brute force is slow

DFS version O(V + E), যা ঠিকঠাক — কিন্তু এতে adjacency list গড়া, recursion stack, parent-tracking, আর শেষে আলাদা connectivity check লাগে; cycle আর connectivity দুটো ভিন্ন logic। DSU একই O(E·α) খরচে দুটোকেই এক union-return-এ মিলিয়ে দেয়, কোনো recursion বা adjacency ছাড়াই — code ছোট, ভুলের জায়গা কম।

11. Key observation

মূল observation: tree = শূন্য cycle + এক component, আর এর একটা চমৎকার সংক্ষিপ্ত রূপ আছে — ঠিক n−1 edge আর শূন্য cycle। edge-সংখ্যা আগে গুনে নিলে, n−1 না হলেই তাড়াতাড়ি False; n−1 হলে শুধু cycle না-থাকা যাচাই করলেই connectivity নিশ্চিত।

12. Optimized intuition

প্রথমে len(edges) != n-1 হলে সরাসরি False। নাহলে সব edge union করো; কোনো union False ফেরালে cycle ⇒ False। সব edge সফলভাবে merge হলে ⇒ True। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(n)।

13. Thinking tweak

মোচড়: "DFS দিয়ে cycle খুঁজি, আবার আলাদা করে connectivity দেখি" — এই দুই-ধাপের চিন্তা ছাড়ো। বদলে ভাবো "n−1 edge গুনে নিই, তারপর একটাও cycle আছে কি না দেখি — না থাকলেই tree।" Edge-গোনা শর্তটাই connectivity-র কাজটা বিনামূল্যে করে দেয়।

14. Step-by-step dry run

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

  1. edge-সংখ্যা = 4 = n−1 → শুরুর check পাস
  2. union(0,1) → roots আলাদা, merge সফল → {0,1}
  3. union(0,2) → merge সফল → {0,1,2}
  4. union(0,3) → merge সফল → {0,1,2,3}
  5. union(1,4) → find(1)=0, find(4)=4, merge সফল → {0,1,2,3,4}
  6. কোনো union False ফেরায়নি → cycle নেই → return True

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 -> cycle
        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_tree(n, edges):
    if len(edges) != n - 1:             # tree-র ঠিক n-1 edge লাগে
        return False
    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):         # False -> দুটো node আগেই যুক্ত -> cycle
            return False
    return True                          # n-1 edge + শূন্য cycle -> tree


# ---- tests ----
assert valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
assert valid_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
assert valid_tree(4, [[0, 1], [2, 3]]) is False     # disconnected
assert valid_tree(1, []) is True                    # একটাই node
assert valid_tree(2, [[0, 1]]) is True
print("সব test pass!")

16. Line-by-line code explanation

  • if len(edges) != n - 1: return False — tree-র edge-সংখ্যা ঠিক n−1; এই এক লাইন একসাথে "too many edges" (cycle অনিবার্য) আর "too few" (disconnect অনিবার্য) দুটোই ছেঁকে ফেলে।
  • for u, v in edges: if not dsu.union(u, v) — প্রতিটা edge merge করার চেষ্টা; union False মানে u আর v আগেই এক group, অর্থাৎ এই edge একটা cycle বন্ধ করছে।
  • return False (loop-এর ভেতরে) — cycle পাওয়া গেছে, আর tree হতে পারে না।
  • return True — n−1 edge সফলভাবে merge হয়েছে, কোনো cycle নেই; edge-count শর্ত connectivity নিশ্চিত করে, তাই এটাই tree।

17. Output walkthrough

প্রথম test-এ 4 edge (= n−1) সব সফল merge — cycle নেই, True। দ্বিতীয়টায় 5 edge কিন্তু n−1 = 4, তাই edge-count check-এই False (এ ছাড়াও 1-2-3-1 cycle আছে)। তৃতীয়টায় 2 edge কিন্তু n−1 = 3, edge-count মেলে না — False (disconnected)। single-node case-এ 0 edge = n−1, True। শেষে print: সব test pass!।

18. Time complexity

O(E · α(V)) ≈ O(V) — edge-count check O(1); তারপর প্রতিটা edge একটা union, প্রতিটা amortized near-constant (inverse Ackermann, বাস্তবে ≤ 4)। যেহেতু valid হলে E = V−1, খরচ কার্যত O(V)।

19. Space complexity

O(V) — শুধু parent আর size array; কোনো adjacency list বা recursion stack নেই।

20. Common mistakes

  • edge-count shortcut ভুলে গিয়ে শুধু cycle check করা — তখন disconnected case (দুই আলাদা tree) ভুল করে True ফেরে; connectivity আলাদা করে যাচাই করতে হতো।
  • union-এর False return ব্যবহার না করে আলাদা DFS দিয়ে cycle খোঁজা — কাজ করে, কিন্তু অহেতুক জটিল।
  • DSU array-র size n-এর বদলে edge-সংখ্যা দিয়ে নেওয়া।

21. Which basic problem this inherits from

ভিত্তি: এই tracker-এর DSU cycle-detection insight (concept.md-র "union False ফেরালে cycle")। মূল gap-filling fact — "tree + ঠিক একটা extra edge = ঠিক একটা cycle" — ../../09-graphs/concept.md-তেও আছে। DFS দিয়েও tree যাচাই করা যায় (parent-tracking + visited count); graph fixed আর একবার দেখলে DFS সমান fast, কিন্তু DSU-র code ছোট আর cycle+connectivity এক জায়গায়।

22. Similar harder problems

23. Pattern learned

Cycle detection + component count: edge-count আগে যাচাই করো (tree হলে n−1); তারপর সব edge union করো — প্রথম False-ই cycle-closer। n−1 edge + শূন্য cycle ⇒ tree, connectivity আপনাআপনি নিশ্চিত। "is this a valid tree?" জাতীয় প্রশ্নে এই combo সরাসরি খাটে।

24. Final summary

ভবিষ্যতের আমাকে: "valid tree?" দেখলে দুটো জিনিস মনে করো — edge ঠিক n−1 কি না, আর কোনো cycle আছে কি না। DSU-তে প্রথমটা এক len() check, দ্বিতীয়টা union-এর False return। দুটো টিকলেই tree — DFS-এর connectivity-গোনা ছাড়াই।

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