কনটেন্টে যান

DSU: নতুন সংযোগ এলে দলগুলো মিলিয়ে রাখা

অধ্যায়ের সূচি · অনুশীলন ও সমাধান · মূল ধারণা

দুটি শহর একই সড়ক-নেটওয়ার্কে আছে কি না জানতে সব রাস্তা আবার ঘুরতে হবে কেন? নতুন রাস্তা যোগ হলে দুই শহরের দল মিলিয়ে রাখা যায়। DSU এই দলগুলোর membership সংরক্ষণ করে। এটি মূল graph-এর route সংরক্ষণ করে না।

শেখার ক্রম

  1. Find, union ও representative পড়ুন। Representative একটি label; সর্বনিম্ন node হওয়া বাধ্যতামূলক নয়।
  2. Parent array ও forest পাশাপাশি দেখুন। Forest-এর link মূল রাস্তার edge নয়।
  3. Union-by-size এবং path halving-এর code চালান।
  4. Practice tracker থেকে reachability → components → cycle → grouping নিন।

একটি প্রোগ্রাম: নতুন রাস্তার পরে network report

শহর A, B, C, D। প্রতিটি নতুন রাস্তার পরে জানতে হবে কতটি আলাদা দল আছে এবং সবচেয়ে বড় দলে কত শহর।

যোগ হওয়া রাস্তা দলগুলো দল-সংখ্যা সবচেয়ে বড় দল
শুরু {A}, {B}, {C}, {D} 4 1
A–B {A,B}, {C}, {D} 3 2
C–D {A,B}, 2 2
B–C {A,B,C,D} 1 4
A–D {A,B,C,D} 1 4

শেষ রাস্তার দুই endpoint আগেই একই দলে। তাই union(A,D) false ফেরত দেয়; component count কমবে না। Undirected graph-এ এই অতিরিক্ত edge একটি cycle তৈরি করে।

flowchart BT
  B["B"] --> A["A: root, size 4"]
  C["C"] --> A
  D["D"] --> C

এই ছবিতে arrow node → parent। find(D) পথে D → C → A যায়। Full path compression করলে D সরাসরি A-কে point করবে; membership একই থাকবে। শুধু root-এর size নির্ভরযোগ্য: পুরোনো root C-এর size field রেখে দেওয়া হলেও সেটিকে নতুন component-এর size ভাবা যাবে না।

flowchart BT
  B["B"] --> A["A: root, size 4"]
  C["C"] --> A
  D["D"] --> A

কোথায় ব্যবহার করবেন

প্রোগ্রাম Element কী কখন union পরে কী পাবেন
Account merge Email বা account ID একই email শেয়ার করলে একই ব্যক্তির candidate records-এর দল
Network dashboard Computer ID নতুন cable যোগ হলে Connected group ও group size
Image region grouping সক্রিয় pixel পাশের সক্রিয় pixel পেলে Connected region
Kruskal MST Vertex সস্তা edge ভিন্ন দল জুড়লে Cycle ছাড়া নির্বাচিত edge

Account name এক হওয়া মাত্র union করা যাবে না; problem যে shared identifier-কে প্রমাণ হিসেবে দিচ্ছে সেটি ব্যবহার করতে হবে।

সীমাবদ্ধতা বুঝলে ভুল tool বাছবেন না

দরকার DSU উপযুক্ত? বিকল্প/কারণ
কেবল নতুন edge যোগ, অনেক connectivity query হ্যাঁ Union-by-size + compression-এ amortized O(α(n))
দুই node-এর আসল route না BFS/DFS-এর parent রাখুন
Shortest distance না Weight অনুযায়ী BFS/Dijkstra
অনলাইনে edge মুছে দল আলাদা করা সাধারণ DSU পারে না বিশেষ offline/rollback পদ্ধতি লাগে
Directed graph-এর reachability সাধারণ DSU যথেষ্ট নয় Direction হারিয়ে যায়

Road Construction-এর স্থানীয় নোট এবং CSES 1676-এর মূল প্রশ্ন এই report-এর সরাসরি অনুশীলন।