### stould's blog

By stould, 8 years ago, I'm reading about bipartite graphs, but I can't implement It....
I now:
G[V,E]
For each V[white], their friends must to be V[black], and Each friend V[black] must to have friends V[white].

P.S.: The article would have to be in english please.

Translated to english by google translate:  Comments (8)
•  » » » Here is Link with the proofLinkAnd if you want something more practical: bool dfs(int node, int c) { if(color[node] != 0) { if(color[node] == c) { return true; } else { return false; } } color[node] = c; for(int i = 1; i <= n; i++) if(gr[node][i] == 1) { if(!dfs(i, -c)) { return false; } } return true; } If you're using an adjacency and the graph is 1-> based, it's just call: dfs(1, 1); 
 » Bipartite graph could be found by using DFS or BFS. Just run dfs from any vertex and let's take one more variable cur which switches each time(such as 1 and 2). And when two vertices have the same "color", then this graph is not bipartite. It is better to show code: bool bipartite = true; int a[MaxN][MaxN], color[MaxN]; void dfs(int v, int cur){ mark[v] = true; color[v] = cur; // color this vertex as cur for (int i = 0; i < n; i++) if (a[v][i] == 1){ // if there is edge between v and i if (color[i] == cur) { // if color of vertex i is equal to color of v, that is cur bipartite = false; // graph is definitely not bipartite, so return return; } if (!mark[i]) dfs(v, cur==1?2:1); // continue dfs } }; int main(){ ... dfs(0, 1); cout << bipartite; ... } Then, if graph is bipartite, all vertices colored with 1 are in one group and with color 2 is in another respectively.Try to debug this program and try to understand and analyze. It is obviously that there is no edge between two vertices from the same group.Sorry for my poor English)