PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

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++

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)

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.

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

StatusSourceProblem NameDifficultyTagsSolution
CFEasy
Show Tags

Bipartite

Check CF
SilverEasy
Show Tags

Bipartite

External Sol
Baltic OIHardCheck CF
APIOVery Hard

Module Progress:

Give Us Feedback on Graph Two-Coloring!

PrevNext