تست دو‌بخشی بودن گراف

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

برای تست این شرط و افراز به دو مجموعه، میتوانیم از هر دو الگوریتم جست‌و‌جوی عمق‌اول و جست‌و‌جوی سطح‌اول استفاده کنیم. کافیست نحوه علامت گذاری مزاعفی در این دو الگوریتم را به گونه ای اضافه کنیم که از رأس‌های با رنگ ۰ به رأس‌های با رنگ ۱ برویم و برعکس. حال اگر به رأسی با علامت ۱ رسیدیم که همسایه‌ای از آن از قبل رنگ ۱ را داشت، پس در نتیجه دور فرد پیدا شده است و نمیتوان این کار را کرد؛ برای علامت ۰ نیز به همین ترتیب است. حال اگر هیچ یک از این دو حالت اتفاق نیافتد، در نتیجه میتوان این کار را کرد و رأس‌هایی که علامت ۱ را دارند در یک دسته و بقیه را در دسته مقابل قرار می‌دهیم.
دقت کنید که ممکن است گراف نا‌همبند باشد در نتیجه برای تمام رأس‌های دیده نشده این الگوریتم را تکرار میکنیم.

از آنجا که از الگوریتم های پیمایش استفاده میکنیم، مرتبه زمانی برابر مرتبه زمانی جست‌و‌جو ها است که برابر $O(n + e)$ است. $n$ تعداد رأس‌ها و $e$ تعداد یال‌ها است.

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

bipartiteness.cpp

#include <vector>
const int MAXN = 100 * 1000 + 10;
 
bool mark[MAXN];
bool color[MAXN];
vector <int> adj[MAXN];
 
// اگر خروجی تابع ۱ باشد یعنی مؤلفه‌ی v دو‌بخشی است و اگر ۰ باشد یعنی دور فرد دارد.
bool dfs(int v, bool c){
    mark[v] = 1;
    color[v] = c;
    for(int i=0; i<adj[v].size(); i++) {
            int u = adj[v][i];
            if(mrk[u] != 1)
            {
                bool ret = dfs(u, 1-c);  //  با رنگ مخالف وارد رأس همسایه میشویم
                if (ret == 0)
                    return 0;
            }
 
            if(color[u] == c)  //  اگر رنگ همسایه همرنگ این رأس بود
                return 0;
        }
    }
    return 1;
}