017 — Road Construction¶

Source¶

Original source: Competitive-programming dynamic-connectivity exercise
Platform: CSES Problem Set — "Road Construction" — https://cses.fi/problemset/
Topic: disjoint set union
Difficulty: Hard
Pattern: live component count + max component size (প্রতিটা road-এর পর দুটো মান)
Basic idea inherited from: 10-এর size tracking, কিন্তু CP scale-এ (লাখো city, লাখো road, fast I/O মানসিকতা)

1. Problem in simple words¶

n টা city, শুরুতে কোনো road নেই — প্রতিটা city আলাদা। তারপর m টা road একে একে যোগ হয়, প্রতিটা দুটো city জোড়ে। প্রতিটা road যোগ করার ঠিক পরে দুটো জিনিস বলতে হবে: এই মুহূর্তে মোট কতগুলো আলাদা component আছে, আর সবচেয়ে বড় component-এ কত city। উত্তর m লাইন — প্রতি road-এ (components, biggest)।

n=5
roads: (1,2) (1,3) (4,5) (1,4)

(1,2): components 4, biggest 2
(1,3): components 3, biggest 3
(4,5): components 2, biggest 3   <- biggest কমে না, running max
(1,4): components 1, biggest 5

2. Which basic idea does this inherit from?¶

ভিত্তি 10-এর size tracking (#14-এর মতোই union by size-এর size[root]) আর #13-এর live component count। নতুনত্ব হলো scale — CSES-এ n, m দশ লাখ পর্যন্ত, তাই প্রতিটা operation সত্যিই O(α) হওয়া চাই আর fast I/O ভাবতে হয়। DSU এখানে শুধু সঠিক নয়, একমাত্র বাস্তবসম্মত পথ।

3. What is the hidden math or logic?¶

দুটো invariant একসাথে maintain করি:

Component count: শুরুতে n; প্রতিটা সফল union (দুই আলাদা root) ঠিক 1 কমায়; ব্যর্থ union (আগেই এক group) বদলায় না।
Max size (running max): union করার পর নতুন merged root-এর size-কে এ-পর্যন্ত-দেখা সর্বোচ্চের সাথে তুলনা করো। গুরুত্বপূর্ণ: max কখনো কমে না — পরে কোনো road ছোট component জুড়লেও আগে তৈরি হওয়া বড়টা থেকেই যায়।

4. Which data structure is needed?¶

একটা DSU (n+1 element, 1-indexed) size সহ; দুটো scalar — components আর biggest। কোনো adjacency list নেই; road গুলো শুধু union-এর কাঁচামাল।

5. Why this data structure fits¶

প্রশ্ন দুটোই DSU-র জন্মগত: "কয়টা group?" = root গোনা (count invariant দিয়ে maintain), "বড় group কত?" = union by size-এর size[root]। road স্রোতের মতো আসে আর মাঝে query — dynamic connectivity, যেখানে DSU traversal-কে বহু গুণে হারায়। CP scale-এ amortized O(α) প্রতি operation মানে দশ লাখ road-ও milliseconds।

6. Real-life analogy¶

ভাবো একটা দেশে আলাদা আলাদা শহর, প্রথমে কোনো রাস্তাই নেই। সরকার একটা একটা করে রাস্তা বানাচ্ছে। প্রতিটা নতুন রাস্তার পর সংবাদে দুটো খবর — এখন দেশটা কয়টা বিচ্ছিন্ন অঞ্চলে ভাগ (যেখান থেকে অন্য অঞ্চলে গাড়িতে যাওয়া যায় না), আর সবচেয়ে বড় সংযুক্ত অঞ্চলে কতগুলো শহর। যত রাস্তা বাড়ে, বিচ্ছিন্নতা কমে আর বড় অঞ্চল আরও বড় হয় — কখনো ছোট হয় না।

7. Visual explanation¶

প্রতিটা road union; সফল হলে components−1 আর biggest = max(biggest, নতুন size)।

n=5,  roads: (1,2)(1,3)(4,5)(1,4)
'-' = এখনো আলাদা

শুরু:    1  2  3  4  5     components=5  biggest=1

(1,2):   1-2  3  4  5      union ok -> comp 4,  size{1,2}=2 -> biggest 2
         (12)

(1,3):   1-2-3  4  5       union ok -> comp 3,  size{1,2,3}=3 -> biggest 3
         (123)

(4,5):   1-2-3  4-5        union ok -> comp 2,  size{4,5}=2 -> biggest max(3,2)=3
         (123) (45)

(1,4):   1-2-3-4-5         union ok -> comp 1,  size=5 -> biggest 5
         (12345)

output:  (4,2) (3,3) (2,3) (1,5)

8. Example input and output¶

Input : n=5, roads=[(1,2),(1,3),(4,5),(1,4)]   Output: [(4,2),(3,3),(2,3),(1,5)]
Edge  : n=2, roads=[(1,2)]                      Output: [(1,2)]
Edge  : n=3, roads=[(1,2),(1,2)]               Output: [(2,2),(2,2)]   (duplicate road)
Edge  : n=1, roads=[]                          Output: []              (কোনো road নেই)

9. Brute force thinking¶

সরল চিন্তা: প্রতিটা road যোগ করার পর পুরো current graph-এ DFS/BFS দিয়ে সব component আর তাদের size বের করো; সংখ্যা ও সর্বোচ্চ লিখে রাখো।

1) প্রতিটা road-এর পর:
2)    adjacency list-এ edge যোগ করো
3)    পুরো graph DFS করে component সংখ্যা ও size গণনা করো
4)    (count, max size) record করো

10. Why brute force is slow¶

প্রতিটা road-এর পর পুরো graph চষা — O(n + m) প্রতি road, মোট O(m · (n + m))। CSES scale-এ (n, m ~ 10⁶) এটা সম্পূর্ণ অসম্ভব (10¹² operations)। DSU প্রতিটা road কেবল একটা union + দুটো scalar update-এ সারে, পুরোটা O((n + m) · α(n)) ≈ linear — সেকেন্ডের ভগ্নাংশ। এটাই dynamic connectivity-তে DSU-র সিদ্ধান্তমূলক জয়।

11. Key observation¶

মূল observation: দুটো উত্তরই incrementally maintain করা যায় — পুরো graph নতুন করে গোনার দরকার নেই। component count শুধু সফল union-এ কমে; max size একটা running max, কখনো কমে না। তাই road-প্রতি কাজ ধ্রুবক: এক union, count-এ হয়তো −1, biggest-এ হয়তো max।

12. Optimized intuition¶

components = n, biggest = 1 দিয়ে শুরু করো। প্রতিটা road (a,b)-এ union(a,b): সফল হলে components -= 1 আর biggest = max(biggest, size[find(a)]); ব্যর্থ হলে দুটোই অপরিবর্তিত। প্রতিবার (components, biggest) লেখো। CP-তে fast input parsing আর iterative find (recursion নয়) ব্যবহার করো, যাতে 10⁶-এ stack/সময় না ফেটে যায়।

13. Thinking tweak¶

মোচড়: "প্রতিটা road-এর পর component আর max আবার গুনি" — এই recount ছাড়ো। বদলে দুটো চলমান সংখ্যা রাখো আর প্রতিটা road শুধু delta প্রয়োগ করো: সফল union হলে count−1, merged size দিয়ে max আপডেট। global recompute → constant-time update — এটাই চাবি, আর CP scale-এ এটাই বাঁচায়।

14. Step-by-step dry run¶

Input n=5, roads=[(1,2),(1,3),(4,5),(1,4)]; শুরু components=5, biggest=1:

(1,2): union সফল → components 5→4; size{1,2}=2 → biggest max(1,2)=2 → record (4,2)
(1,3): union সফল → components 4→3; size{1,2,3}=3 → biggest 3 → record (3,3)
(4,5): union সফল → components 3→2; size{4,5}=2 → biggest max(3,2)=3 → record (2,3)
(1,4): union সফল → components 2→1; size=5 → biggest 5 → record (1,5)
result = [(4,2),(3,3),(2,3),(1,5)]

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
        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 road_construction(n, roads):
    dsu = DSU(n + 1)                      # 1-indexed cities; index 0 unused
    components = n                        # শুরুতে প্রতিটা city আলাদা
    biggest = 1 if n >= 1 else 0          # বৃহত্তম component-এর size (running max)
    res = []
    for a, b in roads:
        if dsu.union(a, b):              # নতুন কিছু জুড়ল
            components -= 1               # দুই component এক হলো
            biggest = max(biggest, dsu.size[dsu.find(a)])
        # union ব্যর্থ হলে components/biggest অপরিবর্তিত
        res.append((components, biggest))
    return res


# ---- tests ----
res = road_construction(5, [(1, 2), (1, 3), (4, 5), (1, 4)])
assert res == [(4, 2), (3, 3), (2, 3), (1, 5)], res
assert road_construction(1, []) == []                              # কোনো road নেই
assert road_construction(2, [(1, 2)]) == [(1, 2)]
assert road_construction(3, [(1, 2), (1, 2)]) == [(2, 2), (2, 2)]  # duplicate road
print("সব test pass!")

16. Line-by-line code explanation¶

DSU(n + 1) — city 1-indexed; index 0 খালি রাখি যাতে parent/size সরাসরি city-number দিয়ে index করা যায়।
components = n — শুরুতে প্রতিটা city নিজে এক component; সফল union-এ এটা কমবে।
biggest running max — n >= 1 হলে অন্তত 1 (এক city), নইলে 0।
if dsu.union(a, b): — শুধু সফল merge-এ count কমাই; duplicate/already-connected road কিছু বদলায় না।
dsu.size[dsu.find(a)] — merge-এর পর a-র নতুন root-এর size = merged component-এর আকার; এটা দিয়ে max আপডেট।
res.append(...) — প্রতিটা road-এর পর live (components, biggest)।

17. Output walkthrough¶

sample test-এ চারটে সফল union, প্রতিবার component কমে; তৃতীয় road (4,5) একটা ছোট (size 2) component বানায়, কিন্তু biggest 3-ই থাকে (running max কমে না) — তাই (2,3)। শেষ road সব জুড়ে (1,5)। duplicate-road test-এ দ্বিতীয় (1,2) union False ফেরায়, তাই দুই লাইনই (2,2)। n=1, roads=[]-এ output খালি। শেষে print: সব test pass!।

18. Time complexity¶

O((n + m) · α(n)) ≈ O(n + m) — DSU init O(n), প্রতিটা road একটা union/find amortized near-constant। CP scale-এ (10⁶) এটাই বাস্তবসম্মত একমাত্র পথ; fast I/O ধরে নেওয়া হয়।

19. Space complexity¶

O(n) — DSU-র parent+size array; output O(m) লাইন। সাধারণত প্রতি লাইন সঙ্গে সঙ্গে print করে output buffer ছোট রাখা হয়।

20. Common mistakes¶

max size-কে running max না রেখে প্রতিবার নতুন size বসানো — পরে ছোট component এলে biggest ভুল করে কমে যেত।
size[a] (non-root) থেকে size পড়া — size শুধু root-এ নির্ভরযোগ্য; তাই size[find(a)]।
recursive find ব্যবহার করে 10⁶ depth-এ recursion limit/stack overflow ডেকে আনা — iterative find নিরাপদ।
duplicate/already-connected road-কে সফল ধরে components ভুল কমানো; শুধু union True হলেই কমাও।
slow input (line-by-line input()) ব্যবহার — CSES scale-এ TLE; buffered read দরকার (এখানে যুক্তি দেখানো, code interface-নিরপেক্ষ)।

21. Which basic problem this inherits from¶

ভিত্তি: 10-এর size tracking (#14) আর live component count (#13)। নতুন কিছু idea নয় — একই দুই invariant, কিন্তু CP scale-এ একসাথে maintain করা আর fast I/O ভাবা। DSU snippet ../concept.md-র "বারো লাইন"-এ; "components গোনা" demo "Edges stream হতে হতে components গোনা"-তে।

22. Similar harder problems¶

Number of Islands II (streaming grid connectivity) — https://leetcode.com/problems/number-of-islands-ii/ (এই tracker-এর #13)
Making A Large Island (component size) — https://leetcode.com/problems/making-a-large-island/ (#14)
Number of Operations to Make Network Connected (components + spare edges) — https://leetcode.com/problems/number-of-operations-to-make-network-connected/ (#6)

23. Pattern learned¶

Live component count + max size: dynamic connectivity-তে দুটো জনপ্রিয় চলমান মান — কয়টা component আর বৃহত্তম component কত — দুটোই DSU দিয়ে constant-time update করা যায়। count শুধু সফল union-এ কমে; max size running max (কখনো কমে না)। CP scale-এ এটা DSU ছাড়া বাস্তবে অসম্ভব — traversal প্রতিবার পুরো graph চষে TLE খায়।

24. Final summary¶

ভবিষ্যতের আমাকে: "প্রতিটা edge-এর পর কয়টা component / বড়টা কত" — বিশেষত বড় (CP) input-এ — সরাসরি DSU ধরো। দুটো scalar চলমান রাখো: সফল union-এ count−1, merged size দিয়ে running max। recount কখনো নয়; iterative find আর fast I/O মনে রাখো। এটাই dynamic connectivity-র সবচেয়ে scale-যোগ্য রূপ।

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