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

یافتن پل‌ها به صورت آنلاین

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

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

پیش از این مقاله‌ای با عنوان یافتن پل‌ها در $O(N+M)$ وجود دارد که این مسئله را با یک پیمایش جستجوی اول عمق حل می‌کند. این الگوریتم بسیار پیچیده‌تر خواهد بود، اما یک مزیت بزرگ دارد: الگوریتم توصیف‌شده در این مقاله به صورت آنلاین کار می‌کند، به این معنی که گراف ورودی لازم نیست از قبل مشخص باشد. یال‌ها یکی‌یکی اضافه می‌شوند و پس از هر افزودن، الگوریتم تمام پل‌ها را در گراف فعلی دوباره می‌شمارد. به عبارت دیگر، این الگوریتم برای کارایی بالا روی یک گراف پویا و در حال تغییر طراحی شده است.

به‌طور دقیق‌تر، صورت مسئله به شرح زیر است: در ابتدا، گراف خالی است و از $n$ رأس تشکیل شده است. سپس زوج رئوس $(a, b)$ را دریافت می‌کنیم که نشان‌دهنده‌ی یک یال اضافه‌شده به گراف است. پس از دریافت هر یال، یعنی پس از افزودن هر یال، تعداد فعلی پل‌ها در گراف را خروجی دهید.

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

الگوریتم شرح داده شده در ادامه در زمان $O(n \log n + m)$ کار می‌کند که $m$ تعداد یال‌ها است. این الگوریتم بر پایه‌ی ساختار داده‌ی مجموعه‌های مجزا (DSU) است. با این حال، پیاده‌سازی در این مقاله زمان $O(n \log n + m \log n)$ را صرف می‌کند، زیرا از نسخه‌ی ساده‌شده‌ی DSU بدون Union by Rank استفاده می‌کند.

الگوریتم

ابتدا بیایید یک مؤلفه‌ی $k$-یال-همبند را تعریف کنیم: این یک مؤلفه‌ی همبندی است که با حذف کمتر از $k$ یال همچنان همبند باقی می‌ماند.

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

الگوریتم شرح داده شده در ادامه، این جنگل و همچنین مؤلفه‌های ۲-یال-همبند را به صراحت نگهداری می‌کند.

واضح است که در ابتدا، وقتی گراف خالی است، شامل $n$ مؤلفه‌ی ۲-یال-همبند است که خودشان به هم متصل نیستند.

هنگام افزودن یال بعدی $(a, b)$، سه حالت ممکن است رخ دهد:

  • هر دو رأس $a$ و $b$ در یک مؤلفه‌ی ۲-یال-همبند قرار دارند - در این صورت این یال پل نیست و چیزی را در ساختار جنگل تغییر نمی‌دهد، بنابراین می‌توانیم از این یال صرف‌نظر کنیم.

    بنابراین، در این حالت تعداد پل‌ها تغییر نمی‌کند.

  • رئوس $a$ و $b$ در مؤلفه‌های همبندی کاملاً متفاوتی قرار دارند، یعنی هر کدام بخشی از یک درخت متفاوت هستند. در این حالت، یال $(a, b)$ به یک پل جدید تبدیل می‌شود و این دو درخت در یک درخت ادغام می‌شوند (و تمام پل‌های قدیمی باقی می‌مانند).

    بنابراین، در این حالت تعداد پل‌ها یک واحد افزایش می‌یابد.

  • رئوس $a$ و $b$ در یک مؤلفه‌ی همبندی، اما در مؤلفه‌های ۲-یال-همبند متفاوتی قرار دارند. در این حالت، این یال به همراه برخی از پل‌های قدیمی یک دور تشکیل می‌دهد. تمام این پل‌ها دیگر پل نخواهند بود و دور حاصل باید در یک مؤلفه‌ی ۲-یال-همبند جدید فشرده شود.

    بنابراین، در این حالت تعداد پل‌ها دو یا بیشتر کاهش می‌یابد.

در نتیجه، کل وظیفه به پیاده‌سازی کارآمد تمام این عملیات بر روی جنگلِ مؤلفه‌های ۲-یال-همبند کاهش می‌یابد.

ساختارهای داده برای ذخیره‌سازی جنگل

تنها ساختار داده‌ای که نیاز داریم مجموعه‌های مجزا (DSU) است. در واقع ما دو نسخه از این ساختار را خواهیم ساخت: یکی برای نگهداری مؤلفه‌های همبندی، و دیگری برای نگهداری مؤلفه‌های ۲-یال-همبند. و علاوه بر این، ساختار درختان در جنگلِ مؤلفه‌های ۲-یال-همبند را از طریق اشاره‌گرها ذخیره می‌کنیم: هر مؤلفه‌ی ۲-یال-همبند، اندیس par[] جد خود را در درخت ذخیره می‌کند.

اکنون به طور منسجم هر عملیاتی را که برای پیاده‌سازی باید یاد بگیریم، بررسی می‌کنیم:

  • بررسی اینکه آیا دو رأس در یک مؤلفه‌ی همبندی / ۲-یال-همبند یکسان قرار دارند یا خیر. این کار با الگوریتم معمول DSU انجام می‌شود، فقط کافی است نمایندگان DSUها را پیدا کرده و مقایسه کنیم.

  • اتصال دو درخت برای یک یال $(a, b)$. از آنجایی که ممکن است نه رأس $a$ و نه رأس $b$ ریشه‌ی درختان خود نباشند، تنها راه برای اتصال این دو درخت، تغییر ریشه‌ی یکی از آنهاست. به عنوان مثال، می‌توانید ریشه‌ی درخت رأس $a$ را تغییر دهید و سپس با تنظیم جد $a$ به $b$، آن را به درخت دیگر متصل کنید.

    با این حال، سؤالی در مورد کارایی عملیات تغییر ریشه مطرح می‌شود: برای تغییر ریشه‌ی درخت با ریشه‌ی $r$ به رأس $v$، لازم است تمام رئوس در مسیر بین $v$ و $r$ را پیمایش کرده و اشاره‌گرهای par[] را در جهت مخالف هدایت کنیم، و همچنین ارجاع به جدها را در DSU مسئول مؤلفه‌های همبندی تغییر دهیم.

    بنابراین، هزینه‌ی تغییر ریشه $O(h)$ است، که $h$ ارتفاع درخت است. می‌توان تخمین بدتری با گفتن اینکه هزینه $O(\text{size})$ است، ارائه داد که $\text{size}$ تعداد رئوس در درخت است. پیچیدگی نهایی تفاوتی نخواهد داشت.

    اکنون یک تکنیک استاندارد را به کار می‌بریم: درختی را که رئوس کمتری دارد، تغییر ریشه می‌دهیم. در این صورت، به طور شهودی واضح است که بدترین حالت زمانی است که دو درخت با اندازه‌های تقریباً برابر با هم ترکیب شوند، اما نتیجه یک درخت با دو برابر اندازه است. این امر اجازه نمی‌دهد این وضعیت بارها اتفاق بیفتد.

    به طور کلی، هزینه‌ی کل را می‌توان به صورت یک رابطه‌ی بازگشتی نوشت:

    $$ T(n) = \max_{k = 1 \ldots n-1} \left\{ T(k) + T(n - k) + O(\min(k, n - k))\right\} $$

    $T(n)$ تعداد عملیات لازم برای به دست آوردن یک درخت با $n$ رأس به وسیله‌ی تغییر ریشه و ادغام درختان است. یک درخت به اندازه‌ی $n$ می‌تواند با ترکیب دو درخت کوچکتر به اندازه‌های $k$ و $n - k$ ایجاد شود. این رابطه‌ی بازگشتی دارای جواب $T(n) = O (n \log n)$ است.

    بنابراین، کل زمان صرف شده برای تمام عملیات تغییر ریشه $O(n \log n)$ خواهد بود اگر همیشه درخت کوچکتر از بین دو درخت را تغییر ریشه دهیم.

    باید اندازه‌ی هر مؤلفه‌ی همبندی را نگهداری کنیم، اما ساختار داده‌ی DSU این امکان را بدون مشکل فراهم می‌کند.

  • جستجوی دوری که با افزودن یال جدید $(a, b)$ تشکیل می‌شود. از آنجایی که $a$ و $b$ از قبل در درخت متصل هستند، باید پایین‌ترین جد مشترک (LCA) رئوس $a$ و $b$ را پیدا کنیم. دور شامل مسیرهایی از $b$ به LCA، از LCA به $a$ و یال $a$ به $b$ خواهد بود.

    پس از یافتن دور، تمام رئوس دور شناسایی‌شده را در یک رأس فشرده می‌کنیم. این بدان معناست که ما از قبل پیچیدگی متناسب با طول دور را داریم، که یعنی می‌توانیم از هر الگوریتم LCA متناسب با طول استفاده کنیم و نیازی به استفاده از الگوریتم سریع نداریم.

    از آنجایی که تمام اطلاعات مربوط به ساختار درخت در آرایه‌ی جد par[] موجود است، تنها الگوریتم LCA معقول به شرح زیر است: رئوس $a$ و $b$ را به عنوان بازدید شده علامت‌گذاری می‌کنیم، سپس به سراغ اجداد آنها par[a] و par[b] می‌رویم و آنها را علامت‌گذاری می‌کنیم، سپس به اجداد آنها پیش می‌رویم و به همین ترتیب ادامه می‌دهیم تا به رأسی برسیم که قبلاً علامت‌گذاری شده است. این رأس همان LCA است که به دنبال آن هستیم، و می‌توانیم با پیمایش مجدد مسیر از $a$ و $b$ به LCA، رئوس روی دور را پیدا کنیم.

    واضح است که پیچیدگی این الگوریتم متناسب با طول دور مورد نظر است.

  • فشرده‌سازی دور با افزودن یک یال جدید $(a, b)$ در یک درخت.

    باید یک مؤلفه‌ی ۲-یال-همبند جدید ایجاد کنیم که شامل تمام رئوس دور شناسایی‌شده باشد (همچنین خود دور شناسایی‌شده می‌تواند شامل چند مؤلفه‌ی ۲-یال-همبند باشد، اما این چیزی را تغییر نمی‌دهد). علاوه بر این، لازم است آنها را به گونه‌ای فشرده کنیم که ساختار درخت مختل نشود و تمام اشاره‌گرهای par[] و دو DSU همچنان صحیح باقی بمانند.

    ساده‌ترین راه برای رسیدن به این هدف، فشرده‌سازی تمام رئوس دور در LCA آنهاست. در واقع، LCA بالاترین رأس در میان رئوس است، یعنی اشاره‌گر جد par[] آن بدون تغییر باقی می‌ماند. برای تمام رئوس دیگر حلقه، نیازی به به‌روزرسانی جدها نیست، زیرا این رئوس به سادگی از بین می‌روند. اما در DSU مؤلفه‌های ۲-یال-همبند، تمام این رئوس به سادگی به LCA اشاره خواهند کرد.

    ما DSU مؤلفه‌های ۲-یال-همبند را بدون بهینه‌سازی Union by rank پیاده‌سازی خواهیم کرد، بنابراین به پیچیدگی $O(\log n)$ به طور متوسط در هر پرس‌وجو خواهیم رسید. برای رسیدن به پیچیدگی $O(1)$ به طور متوسط در هر پرس‌وجو، باید رئوس دور را مطابق با Union by rank ترکیب کنیم و سپس par[] را متناسب با آن تخصیص دهیم.

پیاده‌سازی

در اینجا پیاده‌سازی نهایی کل الگوریتم آمده است.

همانطور که قبلاً ذکر شد، برای سادگی، DSU مؤلفه‌های ۲-یال-همبند بدون Union by rank نوشته شده است، بنابراین پیچیدگی حاصل به طور متوسط $O(\log n)$ خواهد بود.

همچنین در این پیاده‌سازی، خود پل‌ها ذخیره نمی‌شوند، بلکه تنها تعداد آنها bridges نگهداری می‌شود. با این حال، ایجاد یک set از تمام پل‌ها دشوار نخواهد بود.

در ابتدا، تابع init() را فراخوانی می‌کنید که دو DSU را مقداردهی اولیه می‌کند (یک مجموعه‌ی جداگانه برای هر رأس ایجاد کرده و اندازه را برابر با یک قرار می‌دهد) و اجداد par را تنظیم می‌کند.

تابع اصلی add_edge(a, b) است که یک یال جدید را پردازش و اضافه می‌کند.

vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;

void init(int n) {
    par.resize(n);
    dsu_2ecc.resize(n);
    dsu_cc.resize(n);
    dsu_cc_size.resize(n);
    lca_iteration = 0;
    last_visit.assign(n, 0);
    for (int i=0; i<n; ++i) {
        dsu_2ecc[i] = i;
        dsu_cc[i] = i;
        dsu_cc_size[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}

int find_2ecc(int v) {
    if (v == -1)
        return -1;
    return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}

int find_cc(int v) {
    v = find_2ecc(v);
    return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}

void make_root(int v) {
    int root = v;
    int child = -1;
    while (v != -1) {
        int p = find_2ecc(par[v]);
        par[v] = child;
        dsu_cc[v] = root;
        child = v;
        v = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
}

void merge_path (int a, int b) {
    ++lca_iteration;
    vector<int> path_a, path_b;
    int lca = -1;
    while (lca == -1) {
        if (a != -1) {
            a = find_2ecc(a);
            path_a.push_back(a);
            if (last_visit[a] == lca_iteration){
                lca = a;
                break;
                }
            last_visit[a] = lca_iteration;
            a = par[a];
        }
        if (b != -1) {
            b = find_2ecc(b);
            path_b.push_back(b);
            if (last_visit[b] == lca_iteration){
                lca = b;
                break;
                }
            last_visit[b] = lca_iteration;
            b = par[b];
        }

    }

    for (int v : path_a) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
    for (int v : path_b) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
}

void add_edge(int a, int b) {
    a = find_2ecc(a);
    b = find_2ecc(b);
    if (a == b)
        return;

    int ca = find_cc(a);
    int cb = find_cc(b);

    if (ca != cb) {
        ++bridges;
        if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = dsu_cc[a] = b;
        dsu_cc_size[cb] += dsu_cc_size[a];
    } else {
        merge_path(a, b);
    }
}

DSU برای مؤلفه‌های ۲-یال-همبند در وکتور dsu_2ecc ذخیره می‌شود و تابعی که نماینده را برمی‌گرداند find_2ecc(v) است. این تابع بارها در بقیه‌ی کد استفاده می‌شود، زیرا پس از فشرده‌سازی چندین رأس در یک رأس، تمام این رئوس از بین می‌روند و در عوض فقط رأس راهبر (leader)، جد صحیح par را در جنگل مؤلفه‌های ۲-یال-همبند دارد.

DSU برای مؤلفه‌های همبندی در وکتور dsu_cc ذخیره می‌شود و یک وکتور اضافی dsu_cc_size نیز برای ذخیره‌ی اندازه‌ی مؤلفه‌ها وجود دارد. تابع find_cc(v) راهبر مؤلفه‌ی همبندی (که در واقع ریشه‌ی درخت است) را برمی‌گرداند.

عملیات تغییر ریشه درخت make_root(v) همانطور که در بالا توضیح داده شد کار می‌کند: از رأس $v$ از طریق اجداد به سمت رأس ریشه پیمایش می‌کند و هر بار جد par را در جهت مخالف هدایت می‌کند. پیوند به نماینده‌ی مؤلفه‌ی همبندی dsu_cc نیز به‌روزرسانی می‌شود تا به رأس ریشه‌ی جدید اشاره کند. پس از تغییر ریشه، باید اندازه‌ی صحیح مؤلفه‌ی همبندی را به ریشه‌ی جدید اختصاص دهیم. همچنین باید مراقب باشیم که برای به دست آوردن نمایندگان مؤلفه‌ی ۲-یال-همبند، find_2ecc() را فراخوانی کنیم، نه رأسی دیگر که قبلاً فشرده شده است.

تابع یافتن و فشرده‌سازی دور merge_path(a, b) نیز همانطور که در بالا توضیح داده شد، پیاده‌سازی شده است. این تابع با بالا رفتن موازی از گره‌های $a$ و $b$ به دنبال LCA آنها می‌گردد تا زمانی که برای دومین بار به یک رأس برخورد کنیم. برای اهداف کارایی، ما یک شناسه منحصر به فرد برای هر فراخوانی یافتن LCA انتخاب می‌کنیم و رئوس پیمایش شده را با آن علامت‌گذاری می‌کنیم. این کار در زمان $O(1)$ انجام می‌شود، در حالی که رویکردهای دیگر مانند استفاده از set عملکرد بدتری دارند. مسیرهای پیموده شده در وکتورهای path_a و path_b ذخیره می‌شوند و ما از آنها برای پیمایش مجدد تا LCA استفاده می‌کنیم و بدین ترتیب تمام رئوس دور را به دست می‌آوریم. تمام رئوس دور با اتصال به LCA فشرده می‌شوند، از این رو پیچیدگی متوسط $O(\log n)$ است (چون از Union by rank استفاده نمی‌کنیم). تمام یال‌هایی که از آنها عبور می‌کنیم، پل بوده‌اند، بنابراین برای هر یال در دور ۱ واحد کم می‌کنیم.

در نهایت، تابع پرس‌وجو add_edge(a, b) مؤلفه‌های همبندی را که رئوس $a$ و $b$ در آنها قرار دارند، تعیین می‌کند. اگر در مؤلفه‌های همبندی متفاوتی قرار داشته باشند، ریشه‌ی درخت کوچکتر تغییر کرده و سپس به درخت بزرگتر متصل می‌شود. در غیر این صورت، اگر رئوس $a$ و $b$ در یک درخت، اما در مؤلفه‌های ۲-یال-همبند متفاوتی قرار داشته باشند، تابع merge_path(a, b) فراخوانی می‌شود که دور را تشخیص داده و آن را در یک مؤلفه‌ی ۲-یال-همبند فشرده می‌کند.