Disjoint Set Union — গ্রামের রাস্তা মেরামতের পরিকল্পনা

কয়েকটি গ্রামের মধ্যে পুরোনো রাস্তা আছে। প্রথমে প্রতিটি পুরোনো রাস্তা যোগ হওয়ার পরে কয়টি আলাদা connected group থাকছে তা জানাবেন। তারপর প্রস্তাবিত নতুন রাস্তার মধ্যে সর্বনিম্ন মোট খরচে সব গ্রাম যুক্ত করার পরিকল্পনা দেবেন। প্রথম ধাপের connectivity-ই দ্বিতীয় ধাপের starting state।

কোর্সের সঙ্গে সম্পর্ক: Graph connectivity ও greedy reasoning-এর বিস্তার। Screenshot-এর module নাম দেখে DSU বা Kruskal-কে Microsoft কোর্সের নিশ্চিত আলাদা lesson বলা হচ্ছে না; এখানে এগুলো অতিরিক্ত অনুশীলন।

১. আগে যা পড়বেন

ক্রম	উপকরণ	প্রস্তুতির লক্ষ্য
১	DSU ধারণা, ধাপে ধাপে চিত্র	Parent pointer এবং representative কী
২	Find if path exists	একই root মানে connectivity
৩	Redundant connection	একই group-এ edge দিলে cycle তৈরি হয়
৪	Road construction	Component count ও largest component বজায় রাখা
৫	Make network connected	সব group জুড়তে অন্তত components-1 edge কেন

প্রথমে ৪টি node-এ তিনটি union হাতে করুন। Parent array-এর shape আর মূল road graph-এর shape একই হওয়া দরকার নেই—এই পার্থক্য বুঝে নিন।

২. সমস্যা ও contract

road_repair(n, existing, candidates) লিখুন।

• Village ID 0..n-1; রাস্তা undirected। শুরুতে সব village আলাদা।
• existing-এর প্রতিটি (u, v) input order-এ যোগ করুন। প্রতিবার joined অর্থ সত্যিই দুই আলাদা group যুক্ত হয়েছে কি না, components ও largest রিপোর্ট করুন।
• candidates-এর (u, v, cost) নতুন রাস্তা তৈরির সম্ভাবনা। পুরোনো রাস্তা free; সেগুলো বাদ দেওয়া যাবে না। প্রয়োজনীয় candidate বেছে সব village connected করুন এবং minimum total cost দিন।
• সমান cost হলে normalized (min(u,v), max(u,v)) অনুযায়ী edge বাছুন।
• যদি সব village জোড়া না যায়, possible=False, cost=None দিন। repairs তখন minimum-cost spanning forest-এর edge; সম্পূর্ণ সফল repair plan নয়। clusters-এ শেষের connected group-গুলো থাকবে।

সীমা: 1 ≤ n ≤ 100,000, existing ও candidate মিলিয়ে সর্বোচ্চ 200,000 edge, integer cost 0..10⁹। Duplicate road ও self-loop বৈধ; এগুলো নতুন group না জুড়লে উপেক্ষা হবে। Invalid vertex, n ≤ 0 বা negative cost-এ ValueError।

Python

road_repair(
    5,
    [(0, 1), (1, 2), (0, 2)],
    [(2, 3, 4), (1, 3, 8), (3, 4, 2), (0, 4, 10)],
)

flowchart LR
    a["0"] --- b["1"]
    b --- c["2"]
    a --- c
    c -. "নতুন: 4" .- d["3"]
    d -. "নতুন: 2" .- e["4"]

পুরোনো road-এর পরে component count 4, 3, 3; largest size 2, 3, 3। তৃতীয় road নতুন group জোড়ে না। প্রথমে cost 2-এর 3–4, তারপর cost 4-এর 2–3 নিলে সব গ্রাম যুক্ত; total 6।

Python

{
    "history": [
        {"joined": True, "components": 4, "largest": 2},
        {"joined": True, "components": 3, "largest": 3},
        {"joined": False, "components": 3, "largest": 3},
    ],
    "possible": True,
    "cost": 6,
    "repairs": [(3, 4, 2), (2, 3, 4)],
    "clusters": [[0, 1, 2, 3, 4]],
}

৩. Guided milestones

A — DSU-এর দুটি operation

find(x) ও union(a,b) লিখুন। find-এ path compression বা path halving, union-এ ছোট group-কে বড় group-এর নিচে লাগান। union সত্যিই merge করলে True, একই root হলে False।

Invariant: root-এর size তার group-এর node count। Non-root-এর পুরোনো size query-র উত্তর নয়। Checkpoint: union(0,1)-এর পরে find(0)==find(1) এবং root size 2।

B — পুরোনো রাস্তার online report

components=n, largest=1 দিয়ে শুরু করুন। Successful union হলে component count এক কমান, merged size দিয়ে largest update করুন। প্রতিটি existing edge-এর পরে report লিখুন।

Checkpoint: (0,1),(1,2),(0,2)-এ শেষ union False; count দ্বিতীয়বারের তুলনায় কমবে না।

C — একই DSU-তে Kruskal repair

Candidate-গুলো (cost, u, v) অনুযায়ী sort করুন। Edge দুই আলাদা group জুড়লে গ্রহণ করুন। পুরোনো DSU ফেলে নতুন DSU বানাবেন না—তাহলে আগে থাকা রাস্তার সুবিধা হারাবেন।

Invariant: গৃহীত নতুন edge দুই existing component-কে যুক্ত করে; অপ্রয়োজনীয় cycle কিনছে না। Hint: সবচেয়ে কম খরচের crossing edge নেওয়া নিরাপদ—এটাই Kruskal-এর cut reasoning।

Checkpoint: example-এ 3–4 নেওয়ার পরে component 2; 2–3 নিলে 1; cost 8 ও 10-এর proposal আর লাগবে না।

D — সফলতা ও final group audit

প্রতিটি village-এর find করে group বানান। Village-গুলো ascending রাখুন; group-গুলো smallest member অনুযায়ী সাজান। Component এক না হলে success report দেবেন না।

Checkpoint: n=4, proposal শুধু (0,1,2),(2,3,3) হলে group [[0,1],[2,3]], cost=None। Forest-এর edge আছে মানেই সব গ্রাম connected নয়।

৪. Reference ব্যাখ্যা

Connectivity এবং minimum cost কেন ঠিক থাকে

DSU প্রতিটি সময় পর্যন্ত যুক্ত হওয়া village-গুলোর partition ধরে। Cycle edge-এ union ব্যর্থ হওয়া কোনো ত্রুটি নয়; নতুন connectivity নেই বলে count অপরিবর্তিত থাকে।

Existing component-গুলোকে একটি করে super-node ভাবলে বাকি সমস্যা minimum spanning tree। Kruskal-এর কম খরচের non-cycle edge নির্বাচন সেই contracted graph-এ minimum cost দেয়। সব super-node জোড়া অসম্ভব হলে forest পাওয়া যায়; সেজন্য possible আলাদা।

সম্পূর্ণ Python solution · unit test।

৫. Test, complexity ও সীমাবদ্ধতা

Repository root থেকে চালান; download করলে দুই ফাইল practice/-এ রাখুন।

Bash

python -m unittest discover -s practice -p 'test_dsu_lab.py' -v

৮টি test method example, one village, already connected, disconnected proposals, duplicate/zero-cost road, union-size invariant ও invalid input দেখে। ৬০টি seeded ছোট graph-এ সব candidate subset enumerate করে সত্যিকারের minimum cost-এর সঙ্গে ফল মেলায়।

n village, m existing edge, p candidate হলে sorting O(p log p); DSU operation মোট amortized O((n+m+p) α(n)), final group sorting সর্বোচ্চ O(n log n)। Space O(n+m+p) যদি input, proposal copy ও report সব ধরা হয়। α(n) inverse Ackermann function; বাস্তবে খুব ধীরে বাড়ে।

ব্যবহার হয়েছে	এই lab-এ নেই
Path compression, union by size	Rollback DSU, persistent DSU
Connectivity, redundant edge	Edge delete করে dynamic connectivity
Component size ও count	Accounts merge-এর string-to-ID modeling
Kruskal minimum-cost repair	Making a large island-এর neighbor-root deduplication

বাকি pattern-এর জন্য সব DSU problem অনুসরণ করুন।