The question is, guys. I want to check the graph for bipartite by coloring the vertices of one lobe in red and the other in black. There are no edges between the tops of one beat.

Граф задаётся списком смежности: 5 2 3 2 3 4 0 1 0 1 1

The first line - the number of peaks, well, then, I think, is clear.

I run the crawl in depth. The code itself is here:

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

The answer is incorrect:

1st graph share: 0

2nd share of the graph: 1 2 3 4

Correct answer:

1st graph share: 0 1

2nd share of the graph: 2 3 4

What is the problem? Tell me! Thank!

    1 answer 1

    No, wrong. You repaint every vertex black after every round.

    Try passing color as a parameter:

     void dfs_visit(int v, bool red) { used[v] = true; color[v] = red ? "red" : "black"; for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) { if (!used[*it]) dfs_visit(*it, !red); } }

    Update: probably should use the following:

     bool is_bipartite() { std::set<int> painted; std::map<int, bool> color; int start_vertex = 0; while (graph.size() != painted.size()) { // find a non-painted vertex while (painted[start_vertex]) start_vertex++; if (!dfs_visit(start_vertex, true, painted, color)) return false; } // found no problems => return true; } bool dfs_visit(int v, bool color, std::set& painted, std::map<int, bool>& colors) { painted.insert(v); colors[v] = color; for (int next_vertex : graph[v]) { if (painted.find(next_vertex) != painted.end()) // already painted { if (colors[next_vertex] == color) // adjacent vertices, same color return false; } else { if (!dfs_visit(next_vertex, !color)) // paint recursively return false; } } return true; }

    Advantages: you do not need to add a color and flag to the passage in the graph.

    It works only for connected graphs; for disconnected ones, it is necessary to continue coloring until all vertices become colored.

    Update: Updated code, should work for disconnected graphs

    • Did you ask about the numbers in the adjacency list? Vertices are numbered from scratch. The list can be written as: 0: 2 3; 1: 2 3 4; 2: 0 1; 3: 0 1; 4: 1; Vertex "0" is adjacent to vertices "2" and "3", "1" is adjacent to vertices "2", "3", "4", etc. Thanks for the answer! - rekrut
    • @ rekrut1: Yeah, I realized when I carefully read the question. - VladD
    • Thank you, Vlad! - rekrut