Блог пользователя stould

bipartite graphs
Автор stould, 12 лет назад, По-английски 
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
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you give me more information?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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);
      → Ответить