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

e-maxx algorithm original: C/C++ #algorithm #emaxx #graph #matching

Task text is translated from Russian for the selected interface language. Code is left unchanged.

Static

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

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

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

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

Algorithm

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

Implementation

int n;

vector < vector<int> > g;

... чтение graphа ...

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

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

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.