কনটেন্টে যান

003 — Building Roads

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

Problem link ও উৎস

  • Original source: CSES Problem Set — Building Roads
  • Platform: CSES — https://cses.fi/problemset/task/1666
  • Topic: disjoint set union
  • Difficulty: Easy
  • Pattern: components − 1 (connect all components)
  • Basic idea inherited from: ../../09-graphs/-এর connected-components; এখানে component গুনে তাদের জোড়ার রাস্তা ছাপাই

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

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

n টা city আর m টা existing road দেওয়া। তোমাকে বলতে হবে — সব city-কে একসাথে যুক্ত করতে সবচেয়ে কম কয়টা নতুন road লাগবে, আর কোন কোন জোড়া city-র মধ্যে সেগুলো বানাতে হবে। (CSES-এ city 1..n; আমরা ভেতরে 0-indexed ধরব।)

উদাহরণ
n = 4, roads = (1-2) (3-4)      [0-indexed: (0-1) (2-3)]

দুটো আলাদা দল: {1,2} আর {3,4}
এক রাস্তা যোগ করলেই সব যুক্ত  ->  উত্তর: 1 রাস্তা, যেমন (2-4)

Input ও output

উদাহরণ
Input : n=4, roads=[(0,1),(2,3)]
Output: 1,  [(0,2)]

Input : n=5, roads=[]
Output: 4,  [(0,1),(1,2),(2,3),(3,4)]      (সবাই একা -> শেকল)

Input : n=3, roads=[(0,1),(1,2)]
Output: 0,  []                              (আগেই যুক্ত)

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

ভাবো কয়েকটা আলাদা দ্বীপপুঞ্জ, প্রতিটায় ভেতরে সেতু আছে কিন্তু একে অপরের সাথে নেই। সব দ্বীপপুঞ্জকে এক করতে তুমি একটার সাথে আরেকটাকে সেতুতে বাঁধো — c টা দ্বীপপুঞ্জ হলে c − 1 সেতুই যথেষ্ট, একটা লম্বা শেকলের মতো।

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

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

মূল ভিত হলো connected components বের করা — ../../09-graphs/-এর সেই কাজ। যখন তুমি জানো কয়টা আলাদা দল আছে, তখন তাদের একটা শেকলে গাঁথতে লাগে ঠিক (দল − 1) টা রাস্তা। DSU দল গোনে আর প্রতি দলের একজন প্রতিনিধি দেয়।

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

লুকানো logic: c টা আলাদা component-কে একটা connected graph বানাতে ন্যূনতম c − 1 edge লাগে — ঠিক যেমন c টা গাছকে একটা বনে নয়, একটা শেকলে বাঁধতে c−1 দড়ি লাগে। বেশি দিলে cycle তৈরি হয় (অপচয়); কম দিলে কেউ বিচ্ছিন্ন থেকে যায়। তাই minimum = c − 1, আর প্রতিটা নতুন road দুটো ভিন্ন component জোড়ে।

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

একটা DSU (parent + size)। প্রথমে existing road union করি; তারপর প্রতিটা component থেকে একজন প্রতিনিধি তুলে তাদের পরপর জুড়ে নতুন road-এর তালিকা বানাই।

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

এটা বিশুদ্ধ component প্রশ্ন — "কয়টা দল আর কাকে কার সাথে জুড়ব?" DSU merge-only দুনিয়ায় road union করে দল গড়ে, আর find দিয়ে প্রতি node-এর প্রতিনিধি দেয়। প্রতিনিধি দেখে আমরা প্রতি দল থেকে একটা করে node বেছে শেকল বানাতে পারি — পথ/দূরত্ব ছাড়াই।

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

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

সরল চিন্তা: adjacency list বানাও, DFS/BFS দিয়ে component বের করো, প্রতিটা component-এর একটা node তালিকায় রাখো, তারপর পরপর জুড়ে দাও।

উদাহরণ
1) DFS দিয়ে প্রতিটা component label করো
2) প্রতি component থেকে একটা প্রতিনিধি নাও
3) প্রতিনিধিদের পরপর জুড়ে c−1 টা road ছাপাও

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

DFS version ঠিকঠাক — O(n + m)। কিন্তু CSES-এর scale-এ (n, m ১০ লাখ পর্যন্ত) recursive DFS-এ stack overflow-এর ভয়, আর adjacency list গড়ার overhead। DSU iterative, array-ভিত্তিক, recursion-হীন — বড় input-এ নিরাপদ ও পরিষ্কার, একই O(n + m)।

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

মূল observation: উত্তরের সংখ্যাটা শুধু component-সংখ্যার উপর নির্ভর — c − 1। কোন road কোথায় বানাবে তার অসংখ্য valid উত্তর; সবচেয়ে সহজ হলো প্রতি component-এর এক প্রতিনিধিকে একটা শেকলে গাঁথা।

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

সব existing road union করো। তারপর find(i) দিয়ে প্রতিটা distinct root-এর প্রথম node সংগ্রহ করো — এরা প্রতিনিধি। প্রতিনিধি k টা হলে তাদের পরপর জুড়ে k − 1 road বানাও। পুরোটা amortized প্রায় O(n + m)।

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

মোচড়: "প্রতিটা জোড়া city-র জন্য কি আলাদা ভাবতে হবে?" — না। প্রশ্নটাকে নামিয়ে আনো "কয়টা দল আছে?"-এ। দল c হলে উত্তর সবসময় c − 1; বাকিটা শুধু প্রতিনিধি বেছে শেকল গাঁথা।

ছবিতে বোঝা

existing road union করো, তারপর প্রতি component-এর এক প্রতিনিধি নিয়ে পরপর জোড়ো।

উদাহরণ
n=5, existing roads: (0-1) (2-3)

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

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

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

প্রতিনিধি: find(0)=0, find(2)=2, find(4)=4   ->   reps = [0, 2, 4]
শেকল: (0-2) (2-4)                  ->   নতুন road = 2  (= components − 1)

       *0----নতুন----*2----নতুন----*4
        |            |
        1            3              এখন সব এক component

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

Input n=5, roads=[(0,1),(2,3)]:

  1. union(0,1) → {0,1}; union(2,3) → {2,3}; node 4 একা
  2. প্রতিনিধি খোঁজা: find(0)=0 (নতুন), find(1)=0 (পুরোনো), find(2)=2 (নতুন), find(3)=2 (পুরোনো), find(4)=4 (নতুন)
  3. reps = [0, 2, 4]
  4. শেকল: (0,2), (2,4) → নতুন road = 2
  5. return 2, [(0,2),(2,4)]

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

Python

Python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n

    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
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True


def building_roads(n, roads):
    dsu = DSU(n)
    for u, v in roads:
        dsu.union(u, v)                  # existing road দিয়ে দল গড়ো
    reps = []
    seen = set()
    for city in range(n):                # প্রতি component-এর প্রথম node
        r = dsu.find(city)
        if r not in seen:
            seen.add(r)
            reps.append(city)
    new_roads = [(reps[i], reps[i + 1]) for i in range(len(reps) - 1)]
    return len(new_roads), new_roads


# ---- tests ----
assert building_roads(4, [(0, 1), (2, 3)]) == (1, [(0, 2)])
assert building_roads(5, []) == (4, [(0, 1), (1, 2), (2, 3), (3, 4)])
assert building_roads(3, [(0, 1), (1, 2)]) == (0, [])      # আগেই যুক্ত
assert building_roads(1, []) == (0, [])                    # একটাই city
print("সব test pass!")

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

  • for u, v in roads: dsu.union(u, v) — সব existing road দিয়ে component গড়ো।
  • seen set + reps list — প্রতিটা distinct root-এর জন্য একবার করে একটা প্রতিনিধি city তুলে রাখি।
  • if r not in seen — একই root আগে দেখা থাকলে আবার নেব না; তাই reps-এ প্রতি component থেকে ঠিক একজন।
  • new_roads = [(reps[i], reps[i+1]) ...] — প্রতিনিধিদের পরপর জুড়ে শেকল; k প্রতিনিধি → k − 1 road।
  • return len(new_roads), new_roads — সংখ্যা আর তালিকা দুটোই।

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

প্রথম test-এ দুই component {0,1},{2,3}; reps=[0,2]; এক road (0,2)। দ্বিতীয়টায় ৫ জন একা; reps=[0,1,2,3,4]; চার road শেকলে। তৃতীয়টায় সব যুক্ত; reps=[0]; কোনো road নয়। single-city-ও 0। শেষে print: সব test pass!।

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

সময়

O((n + m) · α(n)) ≈ O(n + m) — m টা union, n টা find প্রতিনিধি খুঁজতে; প্রতিটা amortized near-constant।

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

O(n) — parent + size + seen + reps, সবই O(n)।

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

  • উত্তর c বলা, c − 1 নয় — একটা শেকল গাঁথতে দল-সংখ্যার চেয়ে একটা কম দড়ি লাগে।
  • প্রতিনিধি বাছার সময় find না করে কাঁচা parent[city] দেখা — flat না হলে ভুল প্রতিনিধি।
  • CSES-এর 1-indexed city ভুলে 0-indexed ছাপানো (input/output-এ ±1 মেলানো জরুরি)।

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

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

ভিত্তি: ../../09-graphs/-এর connected components। DFS-এ তুমি component label করতে; এখানে DSU দিয়ে union করে প্রতিনিধি তুলছ। উত্তরের অঙ্ক (c−1) একই থাকে। বড় CP-scale input-এ DSU-র iterative রূপ recursive DFS-এর চেয়ে নিরাপদ।

পরের অনুশীলন

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

Components − 1: c টা আলাদা দলকে যুক্ত করতে ঠিক c − 1 edge লাগে। DSU দিয়ে দল গুনে প্রতিনিধি শেকলে গাঁথলেই উত্তর তৈরি — connectivity-construction-এর সবচেয়ে সাধারণ formula।

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

ভবিষ্যতের আমাকে: "সব যুক্ত করতে কয়টা নতুন link?" দেখলে আগে component গোনো, তারপর উত্তর = c − 1। প্রতিনিধিদের পরপর জুড়লেই বানানোর road-এর তালিকা মিলবে। এটাই connect-everything প্রশ্নের base formula।

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