Хочу проверить граф на двудольность путём окраски вершин одной доли в красный цвет, а другой в чёрный. Рёбер между вершинами одной доли нет.
Граф задаётся списком смежности:
5
2 3
2 3 4
0 1
0 1
1
Первая строка - кол-во вершин, ну а дальше, думаю, понятно.
Запускаю обход в глубину. Сам код вот он:
void dfs_visit(int v)
{
used[v] = true;
color[v] = "red";
for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++)
{
if (!used[*it])
{
dfs_visit(*it);
color[*it] = "black";
}
}
}
Ответ выдаёт неверный:
1-я доля графа: 0
2-я доля графа: 1 2 3 4
Правильный ответ:
1-я доля графа: 0 1
2-я доля графа: 2 3 4
В чём проблема?