stould's blog

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

| 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.

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

    Can you give me more information?

    • »
      »
      »
      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);