007 — Building Roads

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

Problem link ও উৎস

• Original source: CSES Problem Set — Graph Algorithms
• Platform: CSES — https://cses.fi/problemset/task/1666
• Topic: graphs
• Difficulty: Easy (competitive-programming scale)
• Pattern: connected components (count, then join with components − 1 edges)
• Basic idea inherited from: connected components (এই tracker-এর #4, #6); traversal (../dfs.md, ../bfs.md)

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

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

n টা শহর আছে (1 থেকে n নম্বর) আর m টা ইতিমধ্যে-থাকা রাস্তা, প্রতিটা রাস্তা দুটো শহরকে জোড়ে। তোমাকে আরও কিছু নতুন রাস্তা বানাতে হবে যাতে যেকোনো শহর থেকে যেকোনো শহরে পৌঁছানো যায় (পুরো graph একটাই connected অংশ হয়)। বলো: কমপক্ষে কয়টা নতুন রাস্তা লাগবে, আর কোন কোন শহরজোড়ার মধ্যে বানালে হবে — যেকোনো একটা valid উত্তর দিলেই চলবে।

উদাহরণ

n = 4, রাস্তা: 1-2, 3-4
টুকরো (components): {1,2} আর {3,4}   -> 2 টা টুকরো
সবগুলো জুড়তে লাগে 2 - 1 = 1 টা নতুন রাস্তা, যেমন 2-3

Input ও output

উদাহরণ

Input : n = 4, edges = [(1,2),(3,4)]
Output: 1
        একটা valid রাস্তা: 2 3   (যেকোনো cross-component জোড়া চলবে)

Input : n = 6, edges = [(1,2),(2,3),(4,5)]
Output: 2
        valid রাস্তা: 1 4 / 1 6

Edge case (সব আগেই যুক্ত): n = 3, edges = [(1,2),(2,3)] -> 0 (কোনো নতুন রাস্তা লাগে না)

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

দ্বীপপুঞ্জের কয়েকটা দ্বীপ ভাবো — কিছু দ্বীপের ভেতরে আগে থেকেই রাস্তা আছে, কিন্তু দ্বীপগুলো একে অন্যের থেকে বিচ্ছিন্ন। তুমি সেতু বানিয়ে সবগুলোকে এক ভূখণ্ডে জুড়তে চাও সবচেয়ে কম সেতুতে। প্রতিটা দ্বীপ থেকে একটা করে বন্দর বেছে নাও; প্রথম দ্বীপের বন্দরকে বাকি প্রতিটা দ্বীপের বন্দরের সাথে একটা করে সেতুতে জোড়ো। k টা দ্বীপ হলে লাগে k - 1 টা সেতু — সবগুলো এখন এক হয়ে গেছে।

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

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

মূল ভিত হলো connected components (#4-এর island, #6-এর province)। প্রথমে গুনতে হবে graph-টা এখন কয়টা আলাদা টুকরোয় ভাঙা — সেই components-গোনার reflex হুবহু আগের মতো। তফাত শুধু scale আর input: এটা competitive programming, তাই node সংখ্যা বড় (10^5), edges আলাদা লাইনে আসে, আর recursion limit সাবধানতা লাগে। গোনার পরের ছোট পাটিগণিতটাই নতুন।

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

লুকানো logic দুই ধাপে:

প্রথমত, k টা আলাদা component-কে একটাই connected অংশে জোড়াতে ঠিক k - 1 টা edge লাগে — কম নয়, বেশিও নয়। কারণ প্রতিটা নতুন edge বড়জোর দুটো component-কে এক করতে পারে, মানে component সংখ্যা একবারে এক কমায়; k থেকে 1-এ নামতে তাই k - 1 ধাপ।

দ্বিতীয়ত, কোন জোড়া বানাব — প্রতিটা component থেকে যেকোনো একটা প্রতিনিধি শহর নাও, তারপর প্রথম প্রতিনিধিকে বাকি সবার সাথে জোড়ো (একটা তারার মতো)। তাতে সব component এক হয়ে যায়, ঠিক k - 1 edge-এ।

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

• adjacency list (list of lists, 1-indexed) — m টা edge পড়ে বানানো; undirected, তাই দুই দিকেই।
• visited array — কোন শহর কোন component-এ পড়েছে।
• iterative DFS/BFS (collections.deque) — বড় graph-এ recursion limit ভাঙা ঠেকাতে।
• প্রতিনিধির list — প্রতিটা component থেকে একটা করে শহর, পরে জোড়ার জন্য।

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

Adjacency list fit করে কারণ CP graph sparse আর বড়; matrix হলে O(n^2) memory অসম্ভব হতো (n = 10^5)। iterative traversal fit করে কারণ একটা path-graph 10^5 node গভীর হলে recursive DFS Python-এর ~1000-frame limit গুঁড়িয়ে দেবে — তাই explicit stack/queue নিরাপদ। প্রতিনিধির list fit করে কারণ component এক করতে প্রতিটা টুকরো থেকে মাত্র একটা শহর জানলেই যথেষ্ট।

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

প্রথম সরল উপায়

প্রথম সরল চিন্তা: জোড়া বেছে বেছে রাস্তা বানিয়ে প্রতিবার চেক করা graph এখনো connected হলো কিনা — যেমন যেকোনো দুই শহর নিয়ে রাস্তা বানাও, পুরো graph-এ একটা traversal চালিয়ে দেখো সব শহর এক component-এ এল কিনা; না এলে আরেকটা জোড়া যোগ করে আবার চেক।

উদাহরণ

1) রাস্তা বানাও কোনো (u, v) জোড়ায়
2) পুরো graph traverse করে দেখো সব শহর এক component কিনা
3) না হলে ধাপ 1-এ ফিরে আরেকটা জোড়া; হ্যাঁ হলে থামো

কোথায় বেশি কাজ হচ্ছে

প্রতিটা সম্ভাব্য জোড়ার পর পুরো graph rescan করা মানে বহুবার O(n + m) traversal — জোড়ার সংখ্যা বড় হলে খরচ অসহনীয়, আর কোন জোড়া নেওয়া উচিত তার কোনো দিকনির্দেশ নেই। অথচ একটাই traversal-এ সব component গুনে নিলে উত্তরের সংখ্যা সরাসরি k - 1, আর কোন জোড়া — প্রতিনিধিদের একটা তারায় জুড়ে দিলেই হয়। মোট O(n + m), একবারেই।

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

মূল observation: উত্তর = (component সংখ্যা) − 1, আর জোড়াগুলো = এক প্রতিনিধিকে বাকি প্রতিনিধিদের সাথে যুক্ত করা। তাই পুরো সমস্যাটা নেমে আসে "কয়টা component আর প্রতিটার একটা প্রতিনিধি কে" — সেটা একবারের traversal-এ পাওয়া যায়।

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

adjacency list বানাও। 1 থেকে n শহর scan করো; তাজা শহর পেলে তাকে প্রতিনিধি হিসেবে রাখো আর iterative DFS/BFS চালিয়ে গোটা component visited mark করো। শেষে প্রতিনিধির list-এর দৈর্ঘ্য = component সংখ্যা k; উত্তর k - 1। জোড়াগুলো: reps[0] কে reps[1], reps[2], ..., reps[k-1]-এর সাথে। সব মিলিয়ে O(n + m)।

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

মোচড়: "কোন কোন রাস্তা বানাব, তার সব সমাবেশ ভেবে দেখব" না ভেবে ভাবো "শুধু গুনি কয় টুকরো — উত্তর তো (টুকরো − 1), আর জোড়া যেকোনো একটা প্রতিনিধি-তারা।" search করা থেকে নেমে এসো একটা গণনা + একটা সরল construction-এ।

ছবিতে বোঝা

n = 6, রাস্তা 1-2, 2-3, 4-5 দিয়ে দেখি:

উদাহরণ

component গুলো (DFS দিয়ে গোনা):
  {1, 2, 3}        প্রতিনিধি: 1
  {4, 5}           প্রতিনিধি: 4
  {6}              প্রতিনিধি: 6        <- একা শহরও একটা component

3 টা component -> নতুন রাস্তা = 3 - 1 = 2

প্রথম প্রতিনিধি 1-কে বাকিদের সাথে জোড়ো:
  1 - 4
  1 - 6        ->  এখন সব শহর এক টুকরোয়

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

n = 6, edges (1,2),(2,3),(4,5):

1. adjacency: 1:[2], 2:[1,3], 3:[2], 4:[5], 5:[4], 6:[]। seen সব False, reps = []।
2. শহর 1 তাজা → reps = [1]। DFS দখল করে 1,2,3 (সবাই seen)।
3. শহর 2,3 আগেই seen, এড়াও।
4. শহর 4 তাজা → reps = [1,4]। DFS দখল করে 4,5।
5. শহর 5 আগেই seen। শহর 6 তাজা → reps = [1,4,6]। DFS দখল করে 6।
6. k = len(reps) = 3 → নতুন রাস্তা = 2। জোড়া: (1,4) আর (1,6)। return।

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

Python

Python

from collections import deque


def building_roads(n, edges):
    # 1-indexed adjacency list
    adj = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)              # undirected: দুই দিকেই

    seen = [False] * (n + 1)
    reps = []                         # প্রতিটা component থেকে একটা প্রতিনিধি

    for start in range(1, n + 1):
        if not seen[start]:
            reps.append(start)        # নতুন component-এর প্রতিনিধি
            seen[start] = True        # push করার সময় mark করো
            # iterative BFS: বড় graph-এ recursion limit-নিরাপদ
            q = deque([start])
            while q:
                node = q.popleft()
                for nxt in adj[node]:
                    if not seen[nxt]:
                        seen[nxt] = True
                        q.append(nxt)

    new_roads = [(reps[0], reps[i]) for i in range(1, len(reps))]
    return len(new_roads), new_roads


# ---- tests ----
cnt, roads = building_roads(4, [(1, 2), (3, 4)])
assert cnt == 1
assert len(roads) == 1
# প্রতিটা নতুন road আলাদা component জোড়ে কিনা যাচাই (প্রতিনিধি-তারা)
assert roads == [(1, 3)]

cnt2, roads2 = building_roads(6, [(1, 2), (2, 3), (4, 5)])
assert cnt2 == 2
assert roads2 == [(1, 4), (1, 6)]

cnt3, roads3 = building_roads(3, [(1, 2), (2, 3)])
assert cnt3 == 0                       # সব আগেই যুক্ত
assert roads3 == []

cnt4, roads4 = building_roads(5, [])    # কোনো রাস্তা নেই -> 5 একা component
assert cnt4 == 4
assert roads4 == [(1, 2), (1, 3), (1, 4), (1, 5)]
print("সব test pass!")

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

• adj = [[] for _ in range(n + 1)] — 1-indexed, তাই size n + 1; index 0 অব্যবহৃত।
• adj[u].append(v) / adj[v].append(u) — undirected, edge দুই দিকেই।
• reps.append(start) — নতুন component পেলে তার প্রতিনিধি জমা।
• iterative BFS (deque) — recursive DFS-এর বদলে, কারণ CP-তে graph 10^5 deep হতে পারে আর Python recursion ~1000-এ ভাঙে।
• seen[nxt] = True ঠিক q.append-এর পাশে — push-এর সময় mark, queue-তে পুনরাবৃত্তি ঠেকায়।
• new_roads = [(reps[0], reps[i]) ...] — প্রথম প্রতিনিধিকে বাকিদের সাথে তারার মতো জোড়া, k - 1 টা।

Output মিলিয়ে দেখা

building_roads(4, [(1,2),(3,4)]): components {1,2} (rep 1), {3,4} (rep 3) → k = 2, নতুন রাস্তা 1, জোড়া (1,3)। n=6 case-এ তিন component → 2 রাস্তা (1,4),(1,6)। n=3 সব যুক্ত → 0। n=5 কোনো রাস্তা নেই → 5 component → 4 রাস্তা। সব assert pass, শেষে print: সব test pass!।

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

সময়

O(n + m) — adjacency list বানাতে O(n + m), traversal-এ প্রতিটা শহর একবার pop ও প্রতিটা edge constant-বার দেখা; প্রতিনিধি-জোড়া বানানো O(k) ≤ O(n)।

অতিরিক্ত জায়গা

O(n + m) — adjacency list O(n + m), seen array ও queue O(n), প্রতিনিধির list O(k) ≤ O(n)।

যে ভুলগুলো এড়াতে হবে

• recursive DFS ব্যবহার করে বড় input-এ Python recursion limit crash — CP scale-এ iterative DFS/BFS নাও।
• 0-indexed array বানিয়ে 1-indexed শহরে off-by-one — size n + 1 রাখো।
• উত্তরকে k লেখা, k - 1 নয় — k টা টুকরো জুড়তে k - 1 edge লাগে।
• জোড়াগুলো একই component-এর ভেতরে বানানো — তাতে component কমে না; সবসময় cross-component (প্রতিনিধি) জোড়ো।

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

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

ভিত্তি: connected components গোনা (#4, #6) আর traversal (../dfs.md, ../bfs.md)। এটা সেই একই components reflex, কিন্তু (ক) competitive-programming scale-এ iterative traversal-এর সাবধানতা শেখায়, আর (খ) গোনার পরে একটা ছোট পাটিগণিত (k - 1) ও construction যোগ করে। মূল শিক্ষা: components গুনতে পারা মানেই অনেক "graph-কে এক করো" প্রশ্নের অর্ধেক সমাধান হয়ে যাওয়া।

পরের অনুশীলন

• Number of Provinces (matrix input-এ component) — https://leetcode.com/problems/number-of-provinces/ (এই tracker-এর #6)
• Number of Islands (grid input-এ component) — https://leetcode.com/problems/number-of-islands/ (#4)
• Graph Valid Tree (component + cycle যাচাই) — https://leetcode.com/problems/graph-valid-tree/

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

Components, then count − 1 to join: "সব কিছু এক করতে কয়টা edge লাগবে" = (component সংখ্যা) − 1, আর জোড়াগুলো প্রতিনিধিদের একটা তারায় বেঁধে দাও। CP scale মানে adjacency list + iterative traversal + 1-indexing-এর শৃঙ্খলা। খরচ O(n + m)।

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

ভবিষ্যতের আমাকে: "টুকরো গুনি, উত্তর (টুকরো − 1), জোড়া এক প্রতিনিধি-তারা; আর CP scale-এ iterative DFS/BFS নিই যাতে recursion না ভাঙে।" যখনই 'সবকিছু connect করো / minimum links' দেখবে — আগে components গোনো, তারপর সরল পাটিগণিত আর construction-এ নামো।

---

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