Двудольный граф, как исправить алгоритм?

03 февраля 2022, 12:10

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

#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();
}

Answer 1

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

Answer 2

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

#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;
}