PrevNext
Rare
 0/5

Graph Two-Coloring

Author: Siyong Huang

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

Module Progress:

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.

PrevNext