টপোলজিক্যাল সর্টিং#

আপনাকে $n$ টি ভার্টেক্স এবং $m$ টি এজবিশিষ্ট একটি ডিরেক্টেড গ্রাফ দেওয়া হয়েছে। আপনাকে ভার্টেক্সগুলোর এমন একটি ক্রম বের করতে হবে, যেন প্রতিটি এজ ছোট ইনডেক্সবিশিষ্ট ভার্টেক্স থেকে বড় ইনডেক্সবিশিষ্ট ভার্টেক্সের দিকে যায়।

অন্যভাবে বলতে গেলে, আপনি ভার্টেক্সগুলোর এমন একটি পারমুটেশন (টপোলজিক্যাল অর্ডার) খুঁজে বের করতে চান যা গ্রাফের সমস্ত এজ দ্বারা নির্ধারিত ক্রমের সাথে সামঞ্জস্যপূর্ণ।

নিচে একটি গ্রাফ এবং তার টপোলজিক্যাল অর্ডার দেখানো হলো:

টপোলজিক্যাল অর্ডার অনন্য নাও হতে পারে (উদাহরণস্বরূপ, যদি তিনটি ভার্টেক্স $a$, $b$, $c$ থাকে যেখানে $a$ থেকে $b$ তে এবং $a$ থেকে $c$ তে পাথ আছে কিন্তু $b$ থেকে $c$ তে বা $c$ থেকে $b$ তে কোনো পাথ নেই)। উদাহরণের গ্রাফটিরও একাধিক টপোলজিক্যাল অর্ডার রয়েছে, দ্বিতীয় একটি টপোলজিক্যাল অর্ডার হলো নিম্নরূপ:

টপোলজিক্যাল অর্ডার একেবারেই নাও থাকতে পারে। এটি কেবল তখনই বিদ্যমান থাকে যখন ডিরেক্টেড গ্রাফে কোনো সাইকেল না থাকে। অন্যথায় একটি স্ববিরোধিতা তৈরি হয়: যদি ভার্টেক্স $a$ এবং $b$ সম্বলিত কোনো সাইকেল থাকে, তাহলে $a$-এর ইনডেক্স $b$-এর চেয়ে ছোট হওয়া দরকার (যেহেতু $a$ থেকে $b$ তে পৌঁছানো যায়) এবং একই সাথে বড়ও হওয়া দরকার (যেহেতু $b$ থেকে $a$ তে পৌঁছানো যায়)। এই আর্টিকেলে বর্ণিত অ্যালগরিদমটি কনস্ট্রাকশনের মাধ্যমে এটিও দেখায় যে, প্রতিটি অ্যাসাইক্লিক ডিরেক্টেড গ্রাফে অন্তত একটি টপোলজিক্যাল অর্ডার বিদ্যমান।

একটি সাধারণ সমস্যা যেখানে টপোলজিক্যাল সর্টিং ব্যবহৃত হয় তা হলো নিম্নরূপ। $n$ টি চলক আছে যাদের মান অজানা। কিছু চলকের জন্য আমরা জানি যে একটি অপরটির চেয়ে ছোট। আপনাকে যাচাই করতে হবে এই শর্তগুলো পরস্পরবিরোধী কিনা, এবং যদি না হয়, তাহলে চলকগুলোকে ঊর্ধ্বক্রমে সাজিয়ে আউটপুট দিতে হবে (একাধিক উত্তর সম্ভব হলে যেকোনো একটি আউটপুট দিন)। লক্ষ্য করুন, এটি আসলে $n$ টি ভার্টেক্সবিশিষ্ট একটি গ্রাফের টপোলজিক্যাল অর্ডার বের করার সমস্যা।

অ্যালগরিদম#

এই সমস্যাটি সমাধানের জন্য আমরা ডেপথ-ফার্স্ট সার্চ ব্যবহার করব।

ধরে নিই গ্রাফটি অ্যাসাইক্লিক। ডেপথ-ফার্স্ট সার্চ কী করে?

কোনো ভার্টেক্স $v$ থেকে শুরু করলে, ডিএফএস $v$ থেকে বের হওয়া সমস্ত এজ ধরে ট্রাভার্স করার চেষ্টা করে। যেসব এজের শেষ প্রান্তের ভার্টেক্স ইতিমধ্যে পরিদর্শিত হয়েছে সেগুলোতে এটি থামে, এবং বাকি এজগুলো ধরে এগিয়ে যায় ও তাদের শেষ প্রান্তে রিকার্সিভভাবে অনুসন্ধান চালিয়ে যায়।

সুতরাং, $\text{dfs}(v)$ ফাংশন কলটি শেষ হওয়ার সময়ের মধ্যে, $v$ থেকে রিচেবল সমস্ত ভার্টেক্স হয় সরাসরি (একটি এজের মাধ্যমে) অথবা পরোক্ষভাবে সার্চ দ্বারা পরিদর্শিত হয়ে যায়।

আমরা $\text{dfs}(v)$ শেষ হওয়ার সময় ভার্টেক্স $v$-কে একটি লিস্টে যোগ করি। যেহেতু সমস্ত রিচেবল ভার্টেক্স ইতিমধ্যে পরিদর্শিত হয়ে গেছে, $v$-কে যোগ করার সময় তারা আগে থেকেই লিস্টে থাকবে। গ্রাফের প্রতিটি ভার্টেক্সের জন্য এক বা একাধিক ডেপথ-ফার্স্ট সার্চ চালিয়ে এটি করি। গ্রাফের প্রতিটি ডিরেক্টেড এজ $v \rightarrow u$-এর জন্য, $u$ এই লিস্টে $v$-এর আগে আসবে, কারণ $u$ হলো $v$ থেকে রিচেবল। তাই যদি আমরা এই লিস্টের ভার্টেক্সগুলোকে $n-1, n-2, \dots, 1, 0$ দিয়ে লেবেল করি, তাহলে আমরা গ্রাফের একটি টপোলজিক্যাল অর্ডার পেয়ে যাব। অন্যভাবে বলতে গেলে, লিস্টটি বিপরীত টপোলজিক্যাল অর্ডার উপস্থাপন করে।

এই ব্যাখ্যাগুলো ডিএফএস অ্যালগরিদমের এক্সিট টাইমের পরিপ্রেক্ষিতেও উপস্থাপন করা যায়। ভার্টেক্স $v$-এর এক্সিট টাইম হলো সেই সময় যখন $\text{dfs}(v)$ ফাংশন কলটি শেষ হয় (সময়গুলো $0$ থেকে $n-1$ পর্যন্ত সংখ্যায়িত করা যায়)। সহজেই বোঝা যায় যে যেকোনো ভার্টেক্স $v$-এর এক্সিট টাইম সর্বদা তার থেকে রিচেবল যেকোনো ভার্টেক্সের এক্সিট টাইমের চেয়ে বেশি হবে (যেহেতু তারা $\text{dfs}(v)$ কলের আগে বা কলের সময় পরিদর্শিত হয়)। সুতরাং, কাঙ্ক্ষিত টপোলজিক্যাল অর্ডারিং হলো ভার্টেক্সগুলোকে তাদের এক্সিট টাইমের উতরক্রমে সাজানো।

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

এখানে একটি ইমপ্লিমেন্টেশন দেওয়া হলো যেখানে ধরে নেওয়া হয়েছে যে গ্রাফটি অ্যাসাইক্লিক, অর্থাৎ কাঙ্ক্ষিত টপোলজিক্যাল অর্ডারিং বিদ্যমান। প্রয়োজন হলে, আপনি সহজেই যাচাই করতে পারেন গ্রাফটি অ্যাসাইক্লিক কিনা, যেমনটি ডেপথ-ফার্স্ট সার্চ আর্টিকেলে বর্ণিত হয়েছে।

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

সমাধানের মূল ফাংশন হলো topological_sort, যেটি ডিএফএস ভেরিয়েবলগুলো ইনিশিয়ালাইজ করে, ডিএফএস চালায় এবং ans ভেক্টরে উত্তর পায়। লক্ষণীয় যে, গ্রাফটি অ্যাসাইক্লিক না হলেও topological_sort-এর ফলাফল কিছুটা অর্থবহ থাকে এই অর্থে যে, যদি ভার্টেক্স $v$ থেকে ভার্টেক্স $u$ রিচেবল হয় কিন্তু উল্টোটা না হয়, তাহলে ফলাফলের অ্যারেতে ভার্টেক্স $v$ সর্বদা $u$-এর আগে আসবে। এই ইমপ্লিমেন্টেশনের এই বৈশিষ্ট্যটি কোসারাজুর অ্যালগরিদমে ব্যবহৃত হয় সাইকেলযুক্ত ডিরেক্টেড গ্রাফে স্ট্রংলি কানেক্টেড কম্পোনেন্ট এবং তাদের টপোলজিক্যাল সর্টিং বের করতে।

টপোলজিক্যাল সর্টিং#

অ্যালগরিদম#

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

অনুশীলন সমস্যা#