017 — Road Construction

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

Problem link ও উৎস

• Original source: Competitive-programming dynamic-connectivity exercise
• Platform: CSES Problem Set — "Road Construction" — https://cses.fi/problemset/task/1676
• 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 মানসিকতা)

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

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

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

Input ও 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 নেই)

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

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

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

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

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

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

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

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

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

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

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

প্রশ্ন দুটোই 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।

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

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

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

উদাহরণ

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

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

প্রতিটা 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-র সিদ্ধান্তমূলক জয়।

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

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

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

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/সময় না ফেটে যায়।

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

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

ছবিতে বোঝা

প্রতিটা 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)

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

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

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

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

Python

Python

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

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

• 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)।

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

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!।

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

সময়

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

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

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

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

• 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-নিরপেক্ষ)।

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

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

ভিত্তি: 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 গোনা"-তে।

পরের অনুশীলন

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

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

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 খায়।

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

ভবিষ্যতের আমাকে: "প্রতিটা 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।