দ্বিতীয় সেরা মিনিমাম স্প্যানিং ট্রি#
একটি মিনিমাম স্প্যানিং ট্রি $T$ হলো প্রদত্ত গ্রাফ $G$-এর জন্য এমন একটি ট্রি যেটি প্রদত্ত গ্রাফের সব ভার্টেক্সকে সংযুক্ত করে এবং সব সম্ভাব্য স্প্যানিং ট্রি-র মধ্যে সব এজের ওয়েট যোগফল সর্বনিম্ন। একটি দ্বিতীয় সেরা এমএসটি $T'$ হলো এমন একটি স্প্যানিং ট্রি, যার গ্রাফ $G$-এর সব সম্ভাব্য স্প্যানিং ট্রি-র মধ্যে সব এজের ওয়েট যোগফল দ্বিতীয় সর্বনিম্ন।
পর্যবেক্ষণ#
ধরি $T$ হলো গ্রাফ $G$-এর মিনিমাম স্প্যানিং ট্রি। পর্যবেক্ষণ করা যায় যে, দ্বিতীয় সেরা মিনিমাম স্প্যানিং ট্রি $T$ থেকে শুধুমাত্র একটি এজ প্রতিস্থাপনে পার্থক্য করে। (এই বিবৃতির প্রমাণের জন্য এখানে সমস্যা ২৩-১ দেখুন)।
তাই আমাদের এমন একটি এজ $e_{new}$ খুঁজতে হবে যেটি $T$-তে নেই, এবং $T$-এর একটি এজ দিয়ে (ধরি $e_{old}$) প্রতিস্থাপন করতে হবে যেন নতুন গ্রাফ $T' = (T \cup \{e_{new}\}) \setminus \{e_{old}\}$ একটি স্প্যানিং ট্রি হয় এবং ওয়েট পার্থক্য ($e_{new} - e_{old}$) সর্বনিম্ন হয়।
ক্রুস্কালের অ্যালগরিদম ব্যবহার করে#
আমরা প্রথমে এমএসটি বের করতে ক্রুস্কালের অ্যালগরিদম ব্যবহার করতে পারি, তারপর শুধু এটি থেকে একটি এজ সরিয়ে অন্য একটি দিয়ে প্রতিস্থাপন করার চেষ্টা করতে পারি।
১. এজগুলো $O(E \log E)$-এ সর্ট করি, তারপর ক্রুস্কাল দিয়ে $O(E)$-এ এমএসটি বের করি। ২. এমএসটি-র প্রতিটি এজের জন্য (আমাদের কাছে $V-1$ টি এজ থাকবে) সেটিকে সাময়িকভাবে এজ তালিকা থেকে বাদ দিই যেন এটি বেছে নেওয়া না যায়। ৩. তারপর, বাকি এজগুলো ব্যবহার করে আবার $O(E)$-এ এমএসটি বের করার চেষ্টা করি। ৪. এমএসটি-র সব এজের জন্য এটি করি, এবং সবগুলোর মধ্যে সেরাটি নিই।
লক্ষ্য করুন: ধাপ ৩-এর জন্য আমাদের এজগুলো আবার সর্ট করার দরকার নেই।
সুতরাং, সামগ্রিক টাইম কমপ্লেক্সিটি হবে $O(E \log V + E + V E)$ = $O(V E)$।
লোয়েস্ট কমন অ্যানসেস্টর (এলসিএ) সমস্যায় মডেলিং#
আগের পদ্ধতিতে আমরা এমএসটি-র একটি এজ সরানোর সব সম্ভাবনা চেষ্টা করেছি। এখানে আমরা ঠিক উল্টোটা করব। আমরা যে এজ ইতোমধ্যে এমএসটি-তে নেই সেগুলো যোগ করার চেষ্টা করব।
১. এজগুলো $O(E \log E)$-এ সর্ট করি, তারপর ক্রুস্কাল দিয়ে $O(E)$-এ এমএসটি বের করি। ২. প্রতিটি এজ $e$ যেটি ইতোমধ্যে এমএসটি-তে নেই, সেটিকে সাময়িকভাবে এমএসটি-তে যোগ করি, একটি সাইকেল তৈরি করি। সাইকেলটি এলসিএ দিয়ে যাবে। ৩. সাইকেলে $e$-এর সমান নয় এমন সর্বোচ্চ ওয়েটের এজ $k$ খুঁজি, $e$ এজের নোডগুলোর প্যারেন্ট ধরে এলসিএ পর্যন্ত গিয়ে। ৪. $k$-কে সাময়িকভাবে সরিয়ে একটি নতুন স্প্যানিং ট্রি তৈরি করি। ৫. ওয়েট পার্থক্য $\delta = weight(e) - weight(k)$ গণনা করি, এবং পরিবর্তিত এজসহ মনে রাখি। ৬. অন্য সব এজের জন্য ধাপ ২ পুনরাবৃত্তি করি, এবং এমএসটি-র সাথে সবচেয়ে কম ওয়েট পার্থক্যের স্প্যানিং ট্রি রিটার্ন করি।
অ্যালগরিদমের টাইম কমপ্লেক্সিটি নির্ভর করে আমরা কীভাবে $k$ গণনা করি, যেগুলো এই অ্যালগরিদমের ধাপ ২-এর সর্বোচ্চ ওয়েট এজ। $O(E \log V)$-এ দক্ষতার সাথে গণনা করার একটি উপায় হলো সমস্যাটিকে লোয়েস্ট কমন অ্যানসেস্টর (এলসিএ) সমস্যায় রূপান্তর করা।
আমরা এমএসটি-কে রুট করে এলসিএ প্রিপ্রসেস করব এবং তাদের অ্যানসেস্টরদের পাথে সর্বোচ্চ এজ ওয়েটও গণনা করব। এটি এলসিএ-র জন্য বাইনারি লিফটিং ব্যবহার করে করা যায়।
এই পদ্ধতির চূড়ান্ত টাইম কমপ্লেক্সিটি $O(E \log V)$।
উদাহরণস্বরূপ:
ছবিতে বামে এমএসটি এবং ডানে দ্বিতীয় সেরা এমএসটি।
প্রদত্ত গ্রাফে ধরি আমরা উপরের নীল ভার্টেক্সে এমএসটি রুট করি, তারপর এমএসটি-তে নেই এমন এজগুলো বেছে নিয়ে আমাদের অ্যালগরিদম চালাই। ধরি প্রথমে বেছে নেওয়া এজটি হলো $(u, v)$ যার ওয়েট ৩৬। এই এজ ট্রি-তে যোগ করলে ৩৬ - ৭ - ২ - ৩৪ সাইকেল তৈরি হয়।
এখন আমরা $\text{LCA}(u, v) = p$ বের করে এই সাইকেলে সর্বোচ্চ ওয়েট এজ খুঁজব। আমরা $u$ থেকে $p$ এবং $v$ থেকে $p$ পাথে সর্বোচ্চ ওয়েট এজ গণনা করি। লক্ষ্য করুন: $\text{LCA}(u, v)$ কিছু ক্ষেত্রে $u$ বা $v$-এর সমানও হতে পারে। এই উদাহরণে আমরা সাইকেলে সর্বোচ্চ এজ ওয়েট হিসেবে ৩৪ ওয়েটের এজ পাব। এই এজ সরিয়ে আমরা একটি নতুন স্প্যানিং ট্রি পাই, যার ওয়েট পার্থক্য মাত্র ২।
এমএসটি-র অংশ নয় এমন অন্য সব এজ দিয়েও এটি করার পর, আমরা দেখতে পাই যে এই স্প্যানিং ট্রিটি সামগ্রিকভাবেও দ্বিতীয় সেরা স্প্যানিং ট্রি ছিল। ১৪ ওয়েটের এজ বেছে নিলে ট্রি-র ওয়েট ৭ বাড়বে, ২৭ ওয়েটের এজ বেছে নিলে ১৪ বাড়বে, ২৮ ওয়েটের এজ বেছে নিলে ২১ বাড়বে, এবং ৩৯ ওয়েটের এজ বেছে নিলে ট্রি-র ওয়েট ৫ বাড়বে।
ইমপ্লিমেন্টেশন#
struct edge {
int s, e, w, id;
bool operator<(const struct edge& other) { return w < other.w; }
};
typedef struct edge Edge;
const int N = 2e5 + 5;
long long res = 0, ans = 1e18;
int n, m, a, b, w, id, l = 21;
vector<Edge> edges;
vector<int> h(N, 0), parent(N, -1), size(N, 0), present(N, 0);
vector<vector<pair<int, int>>> adj(N), dp(N, vector<pair<int, int>>(l));
vector<vector<int>> up(N, vector<int>(l, -1));
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
vector<int> v = {a.first, a.second, b.first, b.second};
int topTwo = -3, topOne = -2;
for (int c : v) {
if (c > topOne) {
topTwo = topOne;
topOne = c;
} else if (c > topTwo && c < topOne) {
topTwo = c;
}
}
return {topOne, topTwo};
}
void dfs(int u, int par, int d) {
h[u] = 1 + h[par];
up[u][0] = par;
dp[u][0] = {d, -1};
for (auto v : adj[u]) {
if (v.first != par) {
dfs(v.first, u, v.second);
}
}
}
pair<int, int> lca(int u, int v) {
pair<int, int> ans = {-2, -3};
if (h[u] < h[v]) {
swap(u, v);
}
for (int i = l - 1; i >= 0; i--) {
if (h[u] - h[v] >= (1 << i)) {
ans = combine(ans, dp[u][i]);
u = up[u][i];
}
}
if (u == v) {
return ans;
}
for (int i = l - 1; i >= 0; i--) {
if (up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]) {
ans = combine(ans, combine(dp[u][i], dp[v][i]));
u = up[u][i];
v = up[v][i];
}
}
ans = combine(ans, combine(dp[u][0], dp[v][0]));
return ans;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int i = 1; i <= m; i++) {
cin >> a >> b >> w; // 1-indexed
edges.push_back({a, b, w, i - 1});
}
sort(edges.begin(), edges.end());
for (int i = 0; i <= m - 1; i++) {
a = edges[i].s;
b = edges[i].e;
w = edges[i].w;
id = edges[i].id;
if (unite_set(a, b)) {
adj[a].emplace_back(b, w);
adj[b].emplace_back(a, w);
present[id] = 1;
res += w;
}
}
dfs(1, 0, 0);
for (int i = 1; i <= l - 1; i++) {
for (int j = 1; j <= n; ++j) {
if (up[j][i - 1] != -1) {
int v = up[j][i - 1];
up[j][i] = up[v][i - 1];
dp[j][i] = combine(dp[j][i - 1], dp[v][i - 1]);
}
}
}
for (int i = 0; i <= m - 1; i++) {
id = edges[i].id;
w = edges[i].w;
if (!present[id]) {
auto rem = lca(edges[i].s, edges[i].e);
if (rem.first != w) {
if (ans > res + w - rem.first) {
ans = res + w - rem.first;
}
} else if (rem.second != -1) {
if (ans > res + w - rem.second) {
ans = res + w - rem.second;
}
}
}
}
cout << ans << "\n";
return 0;
}রেফারেন্স#
১. Competitive Programming-3, by Steven Halim ২. web.mit.edu