У меня есть алгоритм проверки графа на двудольность. Он проходит какие-то тесты, но на одном валиться(Входные данные теста неизвестны). Сам код:
#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();
}