লোয়েস্ট কমন অ্যানসেস্টর - টারজানের অফ-লাইন অ্যালগরিদম#

আমাদের কাছে $n$ নোড বিশিষ্ট একটি ট্রি $G$ আছে এবং $(u, v)$ আকারের $m$ টি কুয়েরি আছে। প্রতিটি কুয়েরি $(u, v)$-র জন্য আমরা $u$ ও $v$ ভার্টেক্সের লোয়েস্ট কমন অ্যানসেস্টর বের করতে চাই, অর্থাৎ সেই নোড যেটি $u$ এবং $v$ উভয়ের অ্যানসেস্টর এবং ট্রি-তে সবচেয়ে বেশি গভীরতায় অবস্থিত। নোড $v$ নিজেও $v$-এর অ্যানসেস্টর, তাই এলসিএ দুটি নোডের একটিও হতে পারে।

এই নিবন্ধে আমরা সমস্যাটি অফ-লাইনে সমাধান করব, অর্থাৎ আমরা ধরে নিচ্ছি যে সব কুয়েরি আগে থেকে জানা, এবং তাই আমরা যেকোনো ক্রমে কুয়েরিগুলোর উত্তর দিতে পারি। নিম্নলিখিত অ্যালগরিদম সব $m$ টি কুয়েরির উত্তর মোট $O(n + m)$ সময়ে দিতে পারে, অর্থাৎ যথেষ্ট বড় $m$-এর জন্য প্রতিটি কুয়েরিতে $O(1)$।

অ্যালগরিদম#

অ্যালগরিদমটির নাম রবার্ট টারজানের নামানুসারে, যিনি ১৯৭৯ সালে এটি আবিষ্কার করেছিলেন এবং ডিসজয়েন্ট সেট ইউনিয়ন ডেটা স্ট্রাকচারেও অনেক অবদান রেখেছিলেন, যেটি এই অ্যালগরিদমে ব্যাপকভাবে ব্যবহৃত হবে।

অ্যালগরিদমটি ট্রি-র একটি DFS ট্রাভার্সাল দিয়ে সব কুয়েরির উত্তর দেয়। একটি কুয়েরি $(u, v)$-র উত্তর দেওয়া হয় $u$ নোডে, যদি $v$ নোড ইতোমধ্যে আগে ভিজিট করা হয়ে থাকে, অথবা উল্টো।

তাহলে ধরি আমরা বর্তমানে $v$ নোডে আছি, আমরা ইতোমধ্যে রিকার্সিভ DFS কল করেছি, এবং কুয়েরি $(u, v)$-র দ্বিতীয় নোড $u$-ও ইতোমধ্যে ভিজিট করেছি। আসুন শিখি কীভাবে এই দুটি নোডের এলসিএ বের করা যায়।

লক্ষ্য করুন যে $\text{LCA}(u, v)$ হয় $v$ নোড নিজে অথবা তার কোনো অ্যানসেস্টর। তাই আমাদের $v$-এর অ্যানসেস্টরদের মধ্যে ($v$ সহ) সবচেয়ে নিচের নোড খুঁজতে হবে যার জন্য $u$ নোড একটি ডিসেন্ডেন্ট। এছাড়াও লক্ষ্য করুন যে একটি নির্দিষ্ট $v$-এর জন্য ট্রি-র ভিজিট করা নোডগুলো একাধিক ডিসজয়েন্ট সেটে বিভক্ত হয়। $v$ নোডের প্রতিটি অ্যানসেস্টর $p$-এর নিজস্ব সেট আছে যেটিতে এই নোড এবং তার চিলড্রেনদের মধ্যে যারা $v$ থেকে ট্রি-র রুট পর্যন্ত পাথের অংশ নয় তাদের রুটযুক্ত সাবট্রিগুলো থাকে। $u$ নোড যে সেটে থাকে সেটি $\text{LCA}(u, v)$ নির্ধারণ করে: এলসিএ হলো সেটের প্রতিনিধি, অর্থাৎ $v$ এবং ট্রি-র রুটের মধ্যকার পাথে অবস্থিত নোড।

আমাদের শুধু দক্ষতার সাথে এই সব সেট বজায় রাখতে শিখতে হবে। এজন্য আমরা DSU ডেটা স্ট্রাকচার প্রয়োগ করি। ইউনিয়ন বাই র‍্যাংক প্রয়োগ করতে, আমরা প্রতিটি সেটের প্রকৃত প্রতিনিধি ($v$ এবং ট্রি-র রুটের মধ্যকার পাথের মান) ancestor অ্যারেতে সংরক্ষণ করি।

আসুন DFS-এর ইমপ্লিমেন্টেশন আলোচনা করি। ধরি আমরা বর্তমানে $v$ নোড ভিজিট করছি। আমরা DSU-তে নোডটিকে একটি নতুন সেটে রাখি, ancestor[v] = v। যথারীতি আমরা $v$-এর সব চিলড্রেন প্রসেস করি। এজন্য আমাদের প্রথমে সেই নোড থেকে রিকার্সিভলি DFS কল করতে হবে, এবং তারপর এই নোডটিকে তার সব সাবট্রিসহ $v$-এর সেটে যোগ করতে হবে। এটি union_sets ফাংশন এবং পরবর্তী অ্যাসাইনমেন্ট ancestor[find_set(v)] = v দিয়ে করা যায় (এটি প্রয়োজনীয়, কারণ union_sets সেটের প্রতিনিধি পরিবর্তন করতে পারে)।

সবশেষে সব চিলড্রেন প্রসেস করার পর আমরা $(u, v)$ আকারের সব কুয়েরির উত্তর দিতে পারি যেখানে $u$ ইতোমধ্যে ভিজিট করা হয়েছে। কুয়েরির উত্তর, অর্থাৎ $u$ এবং $v$-এর এলসিএ, হবে ancestor[find_set(u)] নোড। সহজেই দেখা যায় যে একটি কুয়েরির উত্তর শুধু একবারই দেওয়া হবে।

আসুন এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি নির্ধারণ করি। প্রথমত, DFS-এর জন্য $O(n)$। দ্বিতীয়ত, union_sets ফাংশন কল যা $n$ বার হয়, ফলে সেটিও $O(n)$। এবং তৃতীয়ত, প্রতিটি কুয়েরির জন্য find_set কল, যা $O(m)$ দেয়। সুতরাং মোট টাইম কমপ্লেক্সিটি $O(n + m)$, অর্থাৎ যথেষ্ট বড় $m$-এর জন্য এটি প্রতিটি কুয়েরিতে $O(1)$-এর সমতুল্য।

ইমপ্লিমেন্টেশন#

এখানে এই অ্যালগরিদমের একটি ইমপ্লিমেন্টেশন দেওয়া হলো। DSU-এর ইমপ্লিমেন্টেশন অন্তর্ভুক্ত করা হয়নি, কারণ এটি কোনো পরিবর্তন ছাড়াই ব্যবহার করা যায়।

vector<vector<int>> adj;
vector<vector<int>> queries;
vector<int> ancestor;
vector<bool> visited;

void dfs(int v)
{
    visited[v] = true;
    ancestor[v] = v;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
            union_sets(v, u);
            ancestor[find_set(v)] = v;
        }
    }
    for (int other_node : queries[v]) {
        if (visited[other_node])
            cout << "LCA of " << v << " and " << other_node
                 << " is " << ancestor[find_set(other_node)] << ".\n";
    }
}

void compute_LCAs() {
    // initialize n, adj and DSU
    // for (each query (u, v)) {
    //    queries[u].push_back(v);
    //    queries[v].push_back(u);
    // }

    ancestor.resize(n);
    visited.assign(n, false);
    dfs(0);
}