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.

1#include <cstdio>
2#include <vector>
3
4const int MN = 1e5+10;
5
6int N, M;
7bool bad, vis[MN], group[MN];
8std::vector<int> a[MN];
9
10void dfs(int n=1, bool g=0)

1import java.io.*;
2import java.util.*;
3
4public class BuildingTeams
5{
6    static InputReader in = new InputReader(System.in);
7    static PrintWriter out = new PrintWriter(System.out);
8
9    public static final int MN = 100010;
10    public static final int MM = 200010;

Problems