← Static tasks

E062. Проверка графа на двудольность и разбиение на две доли

emaxx algorithm

#algorithm#emaxx#graph#matching

Task

Источник: e-maxx.ru/algo, страница PDF 188.

Пусть дан неориентированный граф. Требуется проверить, является ли он двудольным, т.е. можно ли разделить его вершины на две доли так, чтобы не было рёбер, соединяющих две вершины одной доли. Если граф является двудольным, то вывести сами доли. Решим эту задачу с помощью поиска в ширину за O (M).

Признак двудольности

Теорема. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют чётную длину. Впрочем, с практической точки зрения искать все простые циклы неудобно. Намного проще проверять граф на двудольность следующим алгоритмом:

Алгоритм

Произведём серию поисков в ширину. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.

Реализация

int n;

vector < vector<int> > g;

... чтение графа ...

vector<char> part (n, -1);

bool ok = true;

vector<int> q (n);

for (int st=0; st<n; ++st)
if (part[st] == -1) {
int h=0, t=0;

q[t++] = st;

part[st] = 0;

while (h<t) {
int v = q[h++];
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (part[to] == -1)

part[to] = !part[v], q[t++] = to;

else

ok &= part[to] != part[v];

} } }

puts (ok ? "YES" : "NO");

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int n;
    vector < List<int> > g;
    ... чтение графа ...
    List<char> part (n, -1);
    bool ok = true;
    List<int> q (n);
    for (int st=0; st<n; ++st)
            if (part[st] == -1) {
                    int h=0, t=0;
                    q[t++] = st;
                    part[st] = 0;
                    while (h<t) {
                            int v = q[h++];
                            for (size_t i=0; i<g[v].size(); ++i) {
                                    int to = g[v][i];
                                    if (part[to] == -1)
                                            part[to] = !part[v],  q[t++] = to;
                                    else
                                            ok &= part[to] != part[v];
                            }
                    }
            }
    puts (ok ? "YES" : "NO");
}

C++ solution

matched/original
int n;
vector < vector<int> > g;
... чтение графа ...
vector<char> part (n, -1);
bool ok = true;
vector<int> q (n);
for (int st=0; st<n; ++st)
        if (part[st] == -1) {
                int h=0, t=0;
                q[t++] = st;
                part[st] = 0;
                while (h<t) {
                        int v = q[h++];
                        for (size_t i=0; i<g[v].size(); ++i) {
                                int to = g[v][i];
                                if (part[to] == -1)
                                        part[to] = !part[v],  q[t++] = to;
                                else
                                        ok &= part[to] != part[v];
                        }
                }
        }
puts (ok ? "YES" : "NO");

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int n;
    vector < ArrayList<Integer> > g;
    ... чтение графа ...
    ArrayList<Character> part (n, -1);
    boolean ok = true;
    ArrayList<Integer> q (n);
    for (int st=0; st<n; ++st)
            if (part[st] == -1) {
                    int h=0, t=0;
                    q[t++] = st;
                    part[st] = 0;
                    while (h<t) {
                            int v = q[h++];
                            for (size_t i=0; i<g[v].size(); ++i) {
                                    int to = g[v][i];
                                    if (part[to] == -1)
                                            part[to] = !part[v],  q[t++] = to;
                                    else
                                            ok &= part[to] != part[v];
                            }
                    }
            }
    puts (ok ? "YES" : "NO");
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.