stould's blog

bipartite graphs
By stould, 12 years ago, In English 
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].

Can you help-me sending some articles about this ?

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

I'm reading about it to solve: http://br.spoj.pl/problems/MESA/

Translated to english by google translate:
http://translate.google.com/translate?hl=pt-BR&sl=pt&tl=en&u=http%3A%2F%2Fbr.spoj.pl%2Fproblems%2FMESA%2F
  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should put your links within the link tags, also, a Bipartite graph doesn't contain odd-length cycles and is bi-colorable, you can try to bi-colorate your graph in a DFS, with the trick of different number for the colors in the visited array.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give me more information?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is Link with the proofLink

      And 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);
      → Reply