Skip to content

003 — Building Roads

Source

  • 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 গুনে তাদের জোড়ার রাস্তা ছাপাই

1. Problem in simple words

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)

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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,  []                              (আগেই যুক্ত)

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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)]

15. Python solution

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!")

16. Line-by-line code explanation

  • 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 — সংখ্যা আর তালিকা দুটোই।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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

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