Rare
0/5

# Graph Two-Coloring

Author: Siyong Huang

### Prerequisites

Introducing bipartite graphs.

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.

Focus Problem – read through this problem before continuing!

## Resources

Resources
CPHBrief solution sketch with diagrams.

## 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.

C++

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

Java

### Warning!

Because Java is so slow, an adjacency list using lists/arraylists results in TLE. Instead, the Java sample code will use the Chinese edge representation.

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

StatusSourceProblem NameDifficultyTagsSolutionURL
CFEasy
Show Tags

Bipartite

Check CF
SilverEasy
Show Tags

Bipartite

External Sol
Baltic OIHardCheck CF
APIOVery Hard

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Graph Two-Coloring!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.