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

e-maxx algorithm оригинал: C/C++ #algorithm #emaxx #graph #matching

Static

Источник: 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# решение

auto-draft, проверить перед отправкой

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++ решение

сопоставлено/оригинал

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 решение

auto-draft, проверить перед отправкой

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");
}

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

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.