Как проверить Эйлеровость графа с известными ребрами между вершинами

Question

Вопрос является учебным, однако содержит мои размышления и собственное полуработающее решение

Задание:

Задан рисунок, состоящий из пронумерованных точек и линий между ними. Напишите программу, которая скажет можно ли нарисовать этот рисунок (провести ручку по всем точкам и линиям), не отрывая руки и при этом не проводя одну линию дважды?

Входные данные: Пeрвая строка содержит число NNN – количество точек (число от 0 до 1000 включительно).
Вторая строка содержит число MMM – количество линий (число от 0 до 1000 включительно).
Далее идет MMM строк, каждая из которых содержит пары номеров точек, соединенных линиями (нумерация точек с 1, между парой точек может быть проведено несколько линий)

Выходные данные: Yes - если можно нарисовать такой рисунок, иначе No

Мои размышления:

По свойствам эйлеровости графа в графе существует эйлеров путь, если:

в этом графе не больше 2 нечетных вершин
все компоненты связанности, кроме, может быть, одной, не содержат ребер.

Таким образом, все, что нужно сделать: в массив записать, сколько ребер приходит в каждую вершину, посчитать количество нечетных вершин и, если их больше 2, то выдать No, иначе Yes. Это первое условие. Сейчас у меня есть такой код, который проходит 9/10 тестов (кроме 4).

Мой код:

int main () {
    int n, m;
    cin >> n >> m;
    int num[n+1];
    
    for (int i = 1; i <= n; i++) num[i] = 0;
    
    int a;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> a;
            num[a]++;
        }
    }
    
    int oddNum = 0;
    bool answer = true;
    for (int i = 0; i < n; i++) {
        if (num[i] == 0) { answer = false; break; }
        else if (num[i] % 2 != 0) oddNum++;
        
    }
    if (answer) {
        if (oddNum > 2) answer = false;
        else answer = true;
    }
    cout << (answer ? "Yes" : "No");
}

Проблема и что я о ней думаю:

Думаю, что проблема во второй части условия про компоненты связности, которых должно быть не больше 1, но я не знаю, как проверить это. Может быть, методом перебора, попробовав от каждой точки пробраться ко всем другим?

Answer 1

Я сейчас понял, что в своем комментарии я на самом деле ошибся. Если, например задан граф из 10 вершин, где 8 из них связаны подряд ребрами 1-2, 2-3, ..., 7-8, а оставшиеся две вершины ребер не имеют, то граф не связный, однако он имеет эйлеров путь.

Чтобы проверить это условие нужно составить реальный граф и попытаться запустить bfs из каждой вершины:

int n, m;
cin >> n >> m;
vector<vector<int>> g(n); // список инцидентных ребер каждой вершины
for (int i = 0; i < m; i++)
{
    int u, v;
    cin >> u >> v;
    g[u - 1].push_back(v - 1);
    g[v - 1].push_back(u - 1);
}

// Проверка нечетности
int count_odd = 0;
for (int i = 0; i < n; i++)
    if (g[i].size() % 2 == 1)
        count_odd++;

// Подсчет количества "больших" компонент
int count_big_comp = 0;
vector<bool> use(n, false); // хранит состояния "посещенности" для всех вершин

// Перебор всех вершин для нахождения всех компонент
for (int i = 0; i < n; i++)
{
    if (use[i]) // Проверка вершины на посещенность в какой-то из прошлых компонент
        continue;
    if (g[i].size() == 0) // Проверка вершины на изолированность
        // Вообще тут по логике должна быть строка use[i] = true, но ее можно опустить
        continue;

    count_big_comp++;

    // bfs от i-той вершины
    queue<int> q;
    q.push(i);
    use[i] = true;
    
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        
        for (int to : g[v])
        {
            if (use[to])
                continue;
            q.push(to);
            use[to] = true;
        }
    }
}

if (count_odd <= 2 && count_big_comp <= 1)
    cout << "YES\n";
else
    cout << "NO\n";

БЛОГ НА HUSL

Как проверить Эйлеровость графа с известными ребрами между вершинами

Ответы (1 шт):