Algoritmo de Grafos

Grafo bipartito, coloracion
http://www.codeforces.com/contest/688/submission/18813583
http://www.codeforces.com/contest/688/submission/18801130
http://www.codeforces.com/contest/687/submission/18786960 tourist interesante como codifica las aristas
http://www.codeforces.com/contest/687/submission/18787163
http://www.codeforces.com/contest/687/submission/18830052
http://www.codeforces.com/contest/688/submission/18796883 me fije en el break;

recursos
http://www.geeksforgeeks.org/bipartite-graph/
http://stackoverflow.com/questions/30486784/how-to-find-if-a-graph-is-bipartite
http://codeforces.com/blog/entry/45770
https://jariasf.wordpress.com/
Componentes Conexas
https://codebreakerscorp.wordpress.com/

video
https://www.youtube.com/watch?v=R60jglxhRUQ

Teoria: a Bipartite graph doesn't contain odd-length cycles and is bi-colorable, you can try to bi-colorate your graph in a DFS
**************

Bipartite graph could be found by using DFS or BFS. Just run dfs from any vertex and let's take one more variable curwhich 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)

*************

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