0

У меня есть алгоритм проверки графа на двудольность. Он проходит какие-то тесты, но на одном валиться(Входные данные теста неизвестны). Сам код:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, M;
vector<int> color;
vector<vector<int>> g;
bool isBipartite = true;
// c = 0, 1, 2 (0 - вершина не покрашена, 1,2 - цвета)
void dfs(int v, int c) {
    color[v] = c;
    for (int u : g[v]) {
        if (color[u] == 0)
            c == 1 ? dfs(u, 2) : dfs(u, 1);
        else if (color[u] == c)
            isBipartite = false;
    }
}

void main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    fin >> N >> M;

    int temp1, temp2;
    g.resize(N);
    color.resize(N);
    fill(color.begin(), color.end(), 0);

    for (int i = 0; i < M; i++) {
        fin >> temp1 >> temp2;
        if (temp1 == temp2)
            isBipartite = false;
        g[temp1 - 1].push_back(temp2 - 1);
        g[temp2 - 1].push_back(temp1 - 1);
    }

    for (int i = 0; i < N; i++) {
        if (color[i] == 0)
            dfs(i, 1);
    }

    if (isBipartite)
        fout << "BIPARTITE";
    else
        fout << "NO";

    fin.close();
    fout.close();
}

2 ответа 2

1

Сделайте из орграфа граф (два ребра вместо 1 дуги).

1

Поделюсь своей реализацией задачки:

#include <bits/stdc++.h>

using namespace std;

vector <int> color;
vector <bool> used;
vector <vector<int>> G;

inline void Impossible()
{
    cout << "No\n";
    exit(0);
}

void coloring(int u)
{
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];

        if (color[v] == 0)
        {
            color[v] = 3 - color[u];
            coloring(v);
        }
        else if (color[u] == color[v])
            Impossible();
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    used.resize(1 + n, false);
    color.resize(1 + n, 0);
    G.resize(1 + n);

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i)
    {
        if ( color[i] == 0 )
        {
            color[i] = 1;
            coloring(i);
        }
    }

    cout << "BIPARTITE\n";
    return 0;
}
3
  • Ваше решение практически такое же, система опять же на каких-то входных данных выдает неверный ответ.
    – james
    4 янв 2020 в 12:22
  • это решение верно, я в другой системе ее тестировал
    – GGO
    4 янв 2020 в 12:46
  • Да я тоже в двух других тестировал все проходило, а тут сразу на первом ошибка. Может быть есть какой то случай который не рассмотрел?
    – james
    4 янв 2020 в 12:48

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.