پرش به محتویات

جهت‌دهی قوی

جهت‌دهی قوی یک گراف بدون جهت، تخصیص یک جهت به هر یال است به طوری که گراف را به یک گراف قویاً همبند تبدیل کند. یعنی، پس از جهت‌دهی، باید بتوانیم با دنبال کردن یال‌های جهت‌دار، از هر رأسی به هر رأس دیگری برویم.

راه‌حل

البته، این کار را نمی‌توان برای هر گرافی انجام داد. یک پل را در یک گراف در نظر بگیرید. باید به آن یک جهت اختصاص دهیم و با این کار، این پل را فقط در یک جهت «قابل عبور» می‌کنیم. این بدان معناست که نمی‌توانیم از یک سر پل به سر دیگر آن برویم، بنابراین نمی‌توانیم گراف را قویاً همبند کنیم.

حال یک DFS را در یک گراف همبند و بدون پل در نظر بگیرید. واضح است که ما از هر رأسی بازدید خواهیم کرد. و از آنجا که هیچ پلی وجود ندارد، می‌توانیم هر یال درخت DFS را حذف کنیم و همچنان قادر خواهیم بود با استفاده از مسیری که شامل حداقل یک یال بازگشتی است، از پایین یال به بالای آن برویم. از این نتیجه می‌شود که از هر رأسی می‌توانیم به ریشه درخت DFS برویم. همچنین، از ریشه درخت DFS می‌توانیم به هر رأسی که بخواهیم برویم. ما یک جهت‌دهی قوی پیدا کردیم!

به عبارت دیگر، برای جهت‌دهی قوی یک گراف همبند و بدون پل، یک DFS روی آن اجرا کنید و یال‌های درخت DFS را به سمت دور شدن از ریشه DFS و تمام یال‌های دیگر را از گره نواده به گره نیا در درخت DFS جهت‌دهی کنید.

این نتیجه که گراف‌های همبند و بدون پل دقیقاً همان گراف‌هایی هستند که جهت‌دهی قوی دارند، قضیه رابینز (Robbins' theorem) نامیده می‌شود.

تعمیم مسئله

بیایید مسئله یافتن یک جهت‌دهی برای گراف را به گونه‌ای در نظر بگیریم که تعداد SCCها کمینه شود.

البته، هر مؤلفه همبندی گراف را می‌توان به طور جداگانه در نظر گرفت. حال، از آنجا که فقط گراف‌های بدون پل به طور قوی قابل جهت‌دهی هستند، بیایید تمام پل‌ها را به طور موقت حذف کنیم. در نهایت به تعدادی مؤلفه بدون پل می‌رسیم (دقیقاً برابر با تعداد مؤلفه‌های اولیه + تعداد پل‌ها) و می‌دانیم که می‌توانیم هر یک از آنها را به طور قوی جهت‌دهی کنیم.

ما فقط مجاز به جهت‌دهی یال‌ها بودیم، نه حذف آنها، اما مشخص می‌شود که می‌توانیم پل‌ها را به طور دلخواه جهت‌دهی کنیم. البته، ساده‌ترین راه برای جهت‌دهی آنها این است که الگوریتم توصیف شده در بالا را بدون تغییر بر روی هر مؤلفه همبند اصلی اجرا کنیم.

پیاده‌سازی

در اینجا، ورودی شامل n — تعداد رأس‌ها، m — تعداد یال‌ها، و سپس m خط است که یال‌ها را توصیف می‌کنند.

خروجی در خط اول شامل کمترین تعداد SCCها است و در خط دوم، رشته‌ای به طول m از کاراکترها قرار دارد. هر کاراکتر یا > است — به این معنی که یال متناظر از ورودی، از رأس سمت چپ به رأس سمت راست (طبق ورودی) جهت‌دهی شده است، یا < — که جهت مخالف را نشان می‌دهد.

این یک الگوریتم جستجوی پل است که برای جهت‌دهی یال‌ها نیز اصلاح شده است. شما همچنین می‌توانید به عنوان گام اول یال‌ها را جهت‌دهی کرده و در گام دوم، تعداد SCCها را در گراف جهت‌دار بشمارید.

vector<vector<pair<int, int>>> adj; // لیست مجاورت - زوج‌های رأس و یال
vector<pair<int, int>> edges;

vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
    static int time = 0;
    low[v] = tin[v] = time++;
    for (auto p : adj[v]) {
        if (edge_used[p.second]) continue;
        edge_used[p.second] = true;
        orient[p.second] = v == edges[p.second].first ? '>' : '<';
        int nv = p.first;
        if (tin[nv] == -1) { // اگر nv هنوز بازدید نشده باشد
            find_bridges(nv);
            low[v] = min(low[v], low[nv]);
            if (low[nv] > tin[v]) {
                // یک پل بین v و nv
                bridge_cnt++;
            }
        } else {
            low[v] = min(low[v], tin[nv]);
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    adj.resize(n);
    tin.resize(n, -1);
    low.resize(n, -1);
    orient.resize(m);
    edges.resize(m);
    edge_used.resize(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edges[i] = {a, b};
    }
    int comp_cnt = 0;
    for (int v = 0; v < n; v++) {
        if (tin[v] == -1) {
            comp_cnt++;
            find_bridges(v);
        }
    }
    printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}

مسائل تمرینی