void twocolor(graph *g)

{

    int i;

    for (i = 1; i <= g->nvertices; i++)

    {

        color[i] = UNCOLORED;

    }

    bipartite = true;

    initialize_search(g);

    for (i = 1; i <= g->nvertices; i++)

    {

        if (discovered[i] == false)

        {

            color[i] = WHITE;

            bfs(g, i);

        }

    }

}

void process_edge(int x, int y)

{

    if ((color[x] == color[y]) && (color[x] != UNCOLORED))

    {

        bipartite = false;

        printf("Warning: not bipartite due to (%d, %d) \n", x, y);

    }

    color[y] = complement(color[x]);

}

enum Color {UNCOLORED, WHITE, BLACK};

bool bipartite;

Color color[MAXV + 1];

Color complement(Color color)

{

    if (color == WHITE) return BLACK;

    if (color == BLACK) return WHITE;

    return UNCOLORED;

}

void bfs(graph *g, int start)

{

    std::queue <int> q;

    

    int v;

    int y;

    edgenode *p;

    

    q.push(start);

    discovered[start] = true;

    

    while(!q.empty())

    {

        v = q.front();

        q.pop();

        process_vertex_early(v);

        processed[v] = true;

        p = g->edges[v];

        while (p != NULL)

        {

            y = p->y;

            if ((processed[y] ==  false) || g->directed)

                process_edge(v, y);

            if (discovered[y] == false)

            {

                q.push(y);

                discovered[y] = true;

                parent[y] = v;

            }

            p = p->next;

        }

        process_vertex_late(v);

    }

}