Graph Two-Coloring

Graph two-coloring refers to assigning a boolean value to each node of the graph, dictated by the edge configuration. The most common example of a two-colored graph is a bipartite graph, in which each edge connects two nodes of opposite colors.

Resources

Solution - Building Teams

The idea is that we can arbitrarily label a node and then run DFS. Every time we visit a new (unvisited) node, we set its color based on the edge rule. When we visit a previously visited node, check to see whether its color matches the edge rule.

#include <cstdio>
#include <vector>

const int MN = 1e5+10;

int N, M;
bool bad, vis[MN], group[MN];
std::vector<int> a[MN];

void dfs(int n=1, bool g=0)

import java.io.*;
import java.util.*;

public class BuildingTeams
{
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static final int MN = 100010;
    public static final int MM = 200010;

Problems