Cycles, Bipartite Graphs and Topological Order
Editorial
Three marks, one question
Course Schedule asks whether every course can be finished when some courses need others first. Draw an edge from each prerequisite to the course that needs it, and the answer is yes exactly when the graph has no cycle: no ring of courses, each waiting for the next. A DFS that remembers what it has seen looks like enough. Here are three ways to mark the courses, on a catalogue of 18 diamonds in a row: two courses both need the course before them, and the next course needs them both. There is no cycle in it:
import sys
import time
sys.setrecursionlimit(10000)
def chain(k): # k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1
adj = [[] for _ in range(n)]
for i in range(k):
a, b, c, nxt = 3 * i, 3 * i + 1, 3 * i + 2, 3 * i + 3
adj[a] += [b, c] # b and c both need a, and the next a needs both
adj[b].append(nxt)
adj[c].append(nxt)
return n, adj
def seen_mark(n, adj): # one mark: a course seen before counts as a cycle
seen = [False] * n
def dfs(u):
seen[u] = True
for v in adj[u]:
if seen[v] or dfs(v):
return True
return False
return any(not seen[u] and dfs(u) for u in range(n))
def path_mark(n, adj): # one mark: on the current path, taken off on the way back
on_path, calls = [False] * n, 0
def dfs(u):
nonlocal calls
calls += 1
on_path[u] = True
for v in adj[u]:
if on_path[v] or dfs(v):
return True
on_path[u] = False
return False
return any(dfs(u) for u in range(n)), calls
def three_states(n, adj): # 0 not seen, 1 on the current path, 2 finished
state, calls = [0] * n, 0
def dfs(u):
nonlocal calls
calls += 1
state[u] = 1
for v in adj[u]:
if state[v] == 1 or (state[v] == 0 and dfs(v)):
return True
state[u] = 2
return False
return any(state[u] == 0 and dfs(u) for u in range(n)), calls
def answer(found):
return "cycle" if found else "no cycle"
small = [path_mark(*chain(k))[1] for k in (14, 16)]
n, adj = chain(18)
print(f"18 diamonds in a row: {n} courses, {sum(map(len, adj))} prerequisites")
print("a mark for seen:", answer(seen_mark(n, adj)))
for name, detect in (("a mark for the path", path_mark), ("three states", three_states)):
start = time.perf_counter()
found, calls = detect(n, adj)
ms = round((time.perf_counter() - start) * 1000)
print(f"{name}: {answer(found)}, {calls} calls, {ms} ms")
if detect is path_mark:
big = calls
print("the path mark's calls for 14, 16 and 18 diamonds:", small[0], small[1], big)
# 18 diamonds in a row: 55 courses, 72 prerequisites
# a mark for seen: cycle
# a mark for the path: no cycle, 4194163 calls, 556 ms
# three states: no cycle, 55 calls, 0 ms
# the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163import java.util.*;
public class Main {
static int n;
static List<List<Integer>> adj;
static boolean[] seen, onPath;
static int[] state;
static long calls;
static void chain(int k) { // k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1;
adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < k; i++) {
int a = 3 * i, b = a + 1, c = a + 2, next = a + 3;
adj.get(a).add(b); // b and c both need a, and the next a needs both
adj.get(a).add(c);
adj.get(b).add(next);
adj.get(c).add(next);
}
}
static boolean seenDfs(int u) { // one mark: a course seen before counts as a cycle
seen[u] = true;
for (int v : adj.get(u)) if (seen[v] || seenDfs(v)) return true;
return false;
}
static boolean pathDfs(int u) { // one mark: on the current path, taken off on the way back
calls++;
onPath[u] = true;
for (int v : adj.get(u)) if (onPath[v] || pathDfs(v)) return true;
onPath[u] = false;
return false;
}
static boolean stateDfs(int u) { // 0 not seen, 1 on the current path, 2 finished
calls++;
state[u] = 1;
for (int v : adj.get(u)) if (state[v] == 1 || (state[v] == 0 && stateDfs(v))) return true;
state[u] = 2;
return false;
}
static boolean seenMark() {
seen = new boolean[n];
for (int u = 0; u < n; u++) if (!seen[u] && seenDfs(u)) return true;
return false;
}
static boolean pathMark() {
onPath = new boolean[n];
calls = 0;
for (int u = 0; u < n; u++) if (pathDfs(u)) return true;
return false;
}
static boolean threeStates() {
state = new int[n];
calls = 0;
for (int u = 0; u < n; u++) if (state[u] == 0 && stateDfs(u)) return true;
return false;
}
static String answer(boolean found) {
return found ? "cycle" : "no cycle";
}
public static void main(String[] args) {
long[] small = new long[2];
int[] ks = {14, 16};
for (int i = 0; i < 2; i++) {
chain(ks[i]);
pathMark();
small[i] = calls;
}
chain(18);
int edges = 0;
for (List<Integer> out : adj) edges += out.size();
System.out.println("18 diamonds in a row: " + n + " courses, " + edges + " prerequisites");
System.out.println("a mark for seen: " + answer(seenMark()));
long start = System.nanoTime();
boolean found = pathMark();
long big = calls;
System.out.println("a mark for the path: " + answer(found) + ", " + calls + " calls, "
+ (System.nanoTime() - start) / 1000000 + " ms");
start = System.nanoTime();
found = threeStates();
System.out.println("three states: " + answer(found) + ", " + calls + " calls, "
+ (System.nanoTime() - start) / 1000000 + " ms");
System.out.println("the path mark's calls for 14, 16 and 18 diamonds: " + small[0] + " " + small[1] + " " + big);
}
}
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 40 ms
// three states: no cycle, 55 calls, 0 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj;
vector<char> seen, onPath;
vector<int> state;
long long calls;
void chain(int k) { // k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1;
adj.assign(n, {});
for (int i = 0; i < k; i++) {
int a = 3 * i, b = a + 1, c = a + 2, next = a + 3;
adj[a] = {b, c}; // b and c both need a, and the next a needs both
adj[b].push_back(next);
adj[c].push_back(next);
}
}
bool seenDfs(int u) { // one mark: a course seen before counts as a cycle
seen[u] = 1;
for (int v : adj[u]) if (seen[v] || seenDfs(v)) return true;
return false;
}
bool pathDfs(int u) { // one mark: on the current path, taken off on the way back
calls++;
onPath[u] = 1;
for (int v : adj[u]) if (onPath[v] || pathDfs(v)) return true;
onPath[u] = 0;
return false;
}
bool stateDfs(int u) { // 0 not seen, 1 on the current path, 2 finished
calls++;
state[u] = 1;
for (int v : adj[u]) if (state[v] == 1 || (state[v] == 0 && stateDfs(v))) return true;
state[u] = 2;
return false;
}
bool seenMark() {
seen.assign(n, 0);
for (int u = 0; u < n; u++) if (!seen[u] && seenDfs(u)) return true;
return false;
}
bool pathMark() {
onPath.assign(n, 0);
calls = 0;
for (int u = 0; u < n; u++) if (pathDfs(u)) return true;
return false;
}
bool threeStates() {
state.assign(n, 0);
calls = 0;
for (int u = 0; u < n; u++) if (state[u] == 0 && stateDfs(u)) return true;
return false;
}
string answer(bool found) { return found ? "cycle" : "no cycle"; }
int main() {
long long small[2];
int ks[2] = {14, 16};
for (int i = 0; i < 2; i++) {
chain(ks[i]);
pathMark();
small[i] = calls;
}
chain(18);
int edges = 0;
for (auto& out : adj) edges += out.size();
cout << "18 diamonds in a row: " << n << " courses, " << edges << " prerequisites\n";
cout << "a mark for seen: " << answer(seenMark()) << "\n";
auto start = chrono::steady_clock::now();
bool found = pathMark();
long long big = calls;
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << "a mark for the path: " << answer(found) << ", " << calls << " calls, " << ms << " ms\n";
start = chrono::steady_clock::now();
found = threeStates();
ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
cout << "three states: " << answer(found) << ", " << calls << " calls, " << ms << " ms\n";
cout << "the path mark's calls for 14, 16 and 18 diamonds: " << small[0] << " " << small[1] << " " << big << "\n";
}
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 17 ms
// three states: no cycle, 55 calls, 0 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163let n, adj, seen, onPath, state, calls;
function chain(k) { // k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1;
adj = Array.from({ length: n }, () => []);
for (let i = 0; i < k; i++) {
const a = 3 * i, b = a + 1, c = a + 2, next = a + 3;
adj[a].push(b, c); // b and c both need a, and the next a needs both
adj[b].push(next);
adj[c].push(next);
}
}
function seenDfs(u) { // one mark: a course seen before counts as a cycle
seen[u] = true;
for (const v of adj[u]) if (seen[v] || seenDfs(v)) return true;
return false;
}
function pathDfs(u) { // one mark: on the current path, taken off on the way back
calls++;
onPath[u] = true;
for (const v of adj[u]) if (onPath[v] || pathDfs(v)) return true;
onPath[u] = false;
return false;
}
function stateDfs(u) { // 0 not seen, 1 on the current path, 2 finished
calls++;
state[u] = 1;
for (const v of adj[u]) if (state[v] === 1 || (state[v] === 0 && stateDfs(v))) return true;
state[u] = 2;
return false;
}
function seenMark() {
seen = new Array(n).fill(false);
for (let u = 0; u < n; u++) if (!seen[u] && seenDfs(u)) return true;
return false;
}
function pathMark() {
onPath = new Array(n).fill(false);
calls = 0;
for (let u = 0; u < n; u++) if (pathDfs(u)) return true;
return false;
}
function threeStates() {
state = new Array(n).fill(0);
calls = 0;
for (let u = 0; u < n; u++) if (state[u] === 0 && stateDfs(u)) return true;
return false;
}
const answer = (found) => (found ? "cycle" : "no cycle");
const small = [14, 16].map((k) => { chain(k); pathMark(); return calls; });
chain(18);
console.log(`18 diamonds in a row: ${n} courses, ${adj.reduce((s, out) => s + out.length, 0)} prerequisites`);
console.log(`a mark for seen: ${answer(seenMark())}`);
let start = performance.now();
let found = pathMark();
const big = calls;
console.log(`a mark for the path: ${answer(found)}, ${calls} calls, ${Math.round(performance.now() - start)} ms`);
start = performance.now();
found = threeStates();
console.log(`three states: ${answer(found)}, ${calls} calls, ${Math.round(performance.now() - start)} ms`);
console.log(`the path mark's calls for 14, 16 and 18 diamonds: ${small[0]} ${small[1]} ${big}`);
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 57 ms
// three states: no cycle, 55 calls, 0 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163let n = 0, calls = 0;
let adj: number[][] = [], seen: boolean[] = [], onPath: boolean[] = [], state: number[] = [];
function chain(k: number): void { // k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1;
adj = Array.from({ length: n }, () => []);
for (let i = 0; i < k; i++) {
const a = 3 * i, b = a + 1, c = a + 2, next = a + 3;
adj[a].push(b, c); // b and c both need a, and the next a needs both
adj[b].push(next);
adj[c].push(next);
}
}
function seenDfs(u: number): boolean { // one mark: a course seen before counts as a cycle
seen[u] = true;
for (const v of adj[u]) if (seen[v] || seenDfs(v)) return true;
return false;
}
function pathDfs(u: number): boolean { // one mark: on the current path, taken off on the way back
calls++;
onPath[u] = true;
for (const v of adj[u]) if (onPath[v] || pathDfs(v)) return true;
onPath[u] = false;
return false;
}
function stateDfs(u: number): boolean { // 0 not seen, 1 on the current path, 2 finished
calls++;
state[u] = 1;
for (const v of adj[u]) if (state[v] === 1 || (state[v] === 0 && stateDfs(v))) return true;
state[u] = 2;
return false;
}
function seenMark(): boolean {
seen = new Array<boolean>(n).fill(false);
for (let u = 0; u < n; u++) if (!seen[u] && seenDfs(u)) return true;
return false;
}
function pathMark(): boolean {
onPath = new Array<boolean>(n).fill(false);
calls = 0;
for (let u = 0; u < n; u++) if (pathDfs(u)) return true;
return false;
}
function threeStates(): boolean {
state = new Array<number>(n).fill(0);
calls = 0;
for (let u = 0; u < n; u++) if (state[u] === 0 && stateDfs(u)) return true;
return false;
}
const answer = (found: boolean): string => (found ? "cycle" : "no cycle");
const small = [14, 16].map((k) => { chain(k); pathMark(); return calls; });
chain(18);
console.log(`18 diamonds in a row: ${n} courses, ${adj.reduce((s, out) => s + out.length, 0)} prerequisites`);
console.log(`a mark for seen: ${answer(seenMark())}`);
let start = performance.now();
let found = pathMark();
const big = calls;
console.log(`a mark for the path: ${answer(found)}, ${calls} calls, ${Math.round(performance.now() - start)} ms`);
start = performance.now();
found = threeStates();
console.log(`three states: ${answer(found)}, ${calls} calls, ${Math.round(performance.now() - start)} ms`);
console.log(`the path mark's calls for 14, 16 and 18 diamonds: ${small[0]} ${small[1]} ${big}`);
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 175 ms
// three states: no cycle, 55 calls, 1 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163using System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
static int n;
static List<int>[] adj;
static bool[] seen, onPath;
static int[] state;
static long calls;
static void Chain(int k) { // k diamonds in a row; an edge u -> v means v needs u
n = 3 * k + 1;
adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
for (int i = 0; i < k; i++) {
int a = 3 * i, b = a + 1, c = a + 2, next = a + 3;
adj[a].Add(b); // b and c both need a, and the next a needs both
adj[a].Add(c);
adj[b].Add(next);
adj[c].Add(next);
}
}
static bool SeenDfs(int u) { // one mark: a course seen before counts as a cycle
seen[u] = true;
foreach (int v in adj[u]) if (seen[v] || SeenDfs(v)) return true;
return false;
}
static bool PathDfs(int u) { // one mark: on the current path, taken off on the way back
calls++;
onPath[u] = true;
foreach (int v in adj[u]) if (onPath[v] || PathDfs(v)) return true;
onPath[u] = false;
return false;
}
static bool StateDfs(int u) { // 0 not seen, 1 on the current path, 2 finished
calls++;
state[u] = 1;
foreach (int v in adj[u]) if (state[v] == 1 || (state[v] == 0 && StateDfs(v))) return true;
state[u] = 2;
return false;
}
static bool SeenMark() {
seen = new bool[n];
for (int u = 0; u < n; u++) if (!seen[u] && SeenDfs(u)) return true;
return false;
}
static bool PathMark() {
onPath = new bool[n];
calls = 0;
for (int u = 0; u < n; u++) if (PathDfs(u)) return true;
return false;
}
static bool ThreeStates() {
state = new int[n];
calls = 0;
for (int u = 0; u < n; u++) if (state[u] == 0 && StateDfs(u)) return true;
return false;
}
static string Answer(bool found) => found ? "cycle" : "no cycle";
static void Main() {
var small = new long[2];
int[] ks = {14, 16};
for (int i = 0; i < 2; i++) {
Chain(ks[i]);
PathMark();
small[i] = calls;
}
Chain(18);
int edges = 0;
foreach (var output in adj) edges += output.Count;
Console.WriteLine($"18 diamonds in a row: {n} courses, {edges} prerequisites");
Console.WriteLine($"a mark for seen: {Answer(SeenMark())}");
var watch = Stopwatch.StartNew();
bool found = PathMark();
long big = calls;
Console.WriteLine($"a mark for the path: {Answer(found)}, {calls} calls, {watch.ElapsedMilliseconds} ms");
watch.Restart();
found = ThreeStates();
Console.WriteLine($"three states: {Answer(found)}, {calls} calls, {watch.ElapsedMilliseconds} ms");
Console.WriteLine($"the path mark's calls for 14, 16 and 18 diamonds: {small[0]} {small[1]} {big}");
}
}
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 29 ms
// three states: no cycle, 55 calls, 1 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163package main
import (
"fmt"
"time"
)
var (
n int
adj [][]int
seen []bool
onPath []bool
state []int
calls int64
)
func chain(k int) { // k diamonds in a row; an edge u -> v means v needs u
n = 3*k + 1
adj = make([][]int, n)
for i := 0; i < k; i++ {
a, b, c, next := 3*i, 3*i+1, 3*i+2, 3*i+3
adj[a] = append(adj[a], b, c) // b and c both need a, and the next a needs both
adj[b] = append(adj[b], next)
adj[c] = append(adj[c], next)
}
}
func seenDfs(u int) bool { // one mark: a course seen before counts as a cycle
seen[u] = true
for _, v := range adj[u] {
if seen[v] || seenDfs(v) {
return true
}
}
return false
}
func pathDfs(u int) bool { // one mark: on the current path, taken off on the way back
calls++
onPath[u] = true
for _, v := range adj[u] {
if onPath[v] || pathDfs(v) {
return true
}
}
onPath[u] = false
return false
}
func stateDfs(u int) bool { // 0 not seen, 1 on the current path, 2 finished
calls++
state[u] = 1
for _, v := range adj[u] {
if state[v] == 1 || (state[v] == 0 && stateDfs(v)) {
return true
}
}
state[u] = 2
return false
}
func seenMark() bool {
seen = make([]bool, n)
for u := 0; u < n; u++ {
if !seen[u] && seenDfs(u) {
return true
}
}
return false
}
func pathMark() bool {
onPath = make([]bool, n)
calls = 0
for u := 0; u < n; u++ {
if pathDfs(u) {
return true
}
}
return false
}
func threeStates() bool {
state = make([]int, n)
calls = 0
for u := 0; u < n; u++ {
if state[u] == 0 && stateDfs(u) {
return true
}
}
return false
}
func answer(found bool) string {
if found {
return "cycle"
}
return "no cycle"
}
func main() {
var small [2]int64
for i, k := range []int{14, 16} {
chain(k)
pathMark()
small[i] = calls
}
chain(18)
edges := 0
for _, out := range adj {
edges += len(out)
}
fmt.Printf("18 diamonds in a row: %d courses, %d prerequisites\n", n, edges)
fmt.Println("a mark for seen:", answer(seenMark()))
start := time.Now()
found := pathMark()
big := calls
fmt.Printf("a mark for the path: %s, %d calls, %d ms\n", answer(found), calls, time.Since(start).Milliseconds())
start = time.Now()
found = threeStates()
fmt.Printf("three states: %s, %d calls, %d ms\n", answer(found), calls, time.Since(start).Milliseconds())
fmt.Printf("the path mark's calls for 14, 16 and 18 diamonds: %d %d %d\n", small[0], small[1], big)
}
// 18 diamonds in a row: 55 courses, 72 prerequisites
// a mark for seen: cycle
// a mark for the path: no cycle, 4194163 calls, 20 ms
// three states: no cycle, 55 calls, 0 ms
// the path mark's calls for 14, 16 and 18 diamonds: 262031 1048449 4194163The first says there's a cycle. It went from the first course down one side of every diamond to the end, came back, took the other side of the last diamond and met a course it had already seen. But seen isn't a cycle: two ways into one course make a diamond, and that's all.
The second marks only the path it's on, taking the mark off on the way back, so a diamond never fools it. But nothing tells it a course is already done, so it walks every path again, from every course: 4,194,163 calls for 55 courses, four times as many for every two diamonds (262,031, 1,048,449 and 4,194,163 for 14, 16 and 18), 556 ms in Python. On a big catalogue it runs out of time.
The third keeps both facts in one of three states for each course: not seen yet, on the path now, or finished. A finished course is never entered again, and only a course on the path now closes a cycle: 55 calls, one per course, and the right answer.
Cycles in undirected graphs, and trees
In an undirected graph every edge goes both ways, so a search always sees the vertex it just came from among its neighbours. That one doesn't count. Any other marked neighbour does: there are two ways to it, so there's a cycle. Keep each vertex's parent in the search and check:
def closing_edge(n, edges): # a marked neighbour that isn't the one we came from closes a cycle
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
seen = [False] * n
for s in range(n): # every part of the graph gets a search of its own
if seen[s]:
continue
seen[s] = True
stack = [(s, -1)]
while stack:
u, parent = stack.pop()
for v in adj[u]:
if v == parent:
continue
if seen[v]:
return u, v
seen[v] = True
stack.append((v, u))
return None
def show(n, edges):
found = closing_edge(n, edges)
tree = len(edges) == n - 1 and found is None # a tree: n - 1 edges and no cycle
cycle = f"cycle closed by {found[0]}-{found[1]}" if found else "no cycle"
print(" ".join(f"{u}-{v}" for u, v in edges) + ":", cycle, "| a tree" if tree else "| not a tree")
show(6, [(0, 1), (1, 2), (2, 0), (3, 4)])
show(6, [(0, 1), (1, 2), (1, 3), (3, 4), (4, 5)])
show(6, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5)])
# 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
# 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
# 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treeimport java.util.*;
public class Main {
static int[] closingEdge(int n, int[][] edges) { // a marked neighbour that isn't the one we came from: a cycle
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
boolean[] seen = new boolean[n];
for (int s = 0; s < n; s++) { // every part of the graph gets a search of its own
if (seen[s]) continue;
seen[s] = true;
ArrayDeque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {s, -1});
while (!stack.isEmpty()) {
int[] top = stack.pop();
int u = top[0], parent = top[1];
for (int v : adj.get(u)) {
if (v == parent) continue;
if (seen[v]) return new int[] {u, v};
seen[v] = true;
stack.push(new int[] {v, u});
}
}
}
return null;
}
static void show(int n, int[][] edges) {
int[] found = closingEdge(n, edges);
boolean tree = edges.length == n - 1 && found == null; // a tree: n - 1 edges and no cycle
StringJoiner s = new StringJoiner(" ");
for (int[] e : edges) s.add(e[0] + "-" + e[1]);
String cycle = found != null ? "cycle closed by " + found[0] + "-" + found[1] : "no cycle";
System.out.println(s + ": " + cycle + (tree ? " | a tree" : " | not a tree"));
}
public static void main(String[] args) {
show(6, new int[][] {{0, 1}, {1, 2}, {2, 0}, {3, 4}});
show(6, new int[][] {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {4, 5}});
show(6, new int[][] {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}});
}
}
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a tree#include <bits/stdc++.h>
using namespace std;
optional<pair<int, int>> closingEdge(int n, const vector<pair<int, int>>& edges) { // a marked neighbour, not
vector<vector<int>> adj(n); // the parent: a cycle
for (auto [u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<char> seen(n, 0);
for (int s = 0; s < n; s++) { // every part of the graph gets a search of its own
if (seen[s]) continue;
seen[s] = 1;
vector<pair<int, int>> stack = {{s, -1}};
while (!stack.empty()) {
auto [u, parent] = stack.back();
stack.pop_back();
for (int v : adj[u]) {
if (v == parent) continue;
if (seen[v]) return pair{u, v};
seen[v] = 1;
stack.push_back({v, u});
}
}
}
return nullopt;
}
void show(int n, const vector<pair<int, int>>& edges) {
auto found = closingEdge(n, edges);
bool tree = (int) edges.size() == n - 1 && !found; // a tree: n - 1 edges and no cycle
for (size_t i = 0; i < edges.size(); i++) cout << (i ? " " : "") << edges[i].first << "-" << edges[i].second;
cout << ": ";
if (found) cout << "cycle closed by " << found->first << "-" << found->second;
else cout << "no cycle";
cout << (tree ? " | a tree" : " | not a tree") << "\n";
}
int main() {
show(6, {{0, 1}, {1, 2}, {2, 0}, {3, 4}});
show(6, {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {4, 5}});
show(6, {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}});
}
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treefunction closingEdge(n, edges) { // a marked neighbour that isn't the one we came from closes a cycle
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const seen = new Array(n).fill(false);
for (let s = 0; s < n; s++) { // every part of the graph gets a search of its own
if (seen[s]) continue;
seen[s] = true;
const stack = [[s, -1]];
while (stack.length) {
const [u, parent] = stack.pop();
for (const v of adj[u]) {
if (v === parent) continue;
if (seen[v]) return [u, v];
seen[v] = true;
stack.push([v, u]);
}
}
}
return null;
}
function show(n, edges) {
const found = closingEdge(n, edges);
const tree = edges.length === n - 1 && found === null; // a tree: n - 1 edges and no cycle
const cycle = found ? `cycle closed by ${found[0]}-${found[1]}` : "no cycle";
console.log(`${edges.map(([u, v]) => `${u}-${v}`).join(" ")}: ${cycle}${tree ? " | a tree" : " | not a tree"}`);
}
show(6, [[0, 1], [1, 2], [2, 0], [3, 4]]);
show(6, [[0, 1], [1, 2], [1, 3], [3, 4], [4, 5]]);
show(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5]]);
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treefunction closingEdge(n: number, edges: [number, number][]): [number, number] | null { // a marked neighbour,
const adj: number[][] = Array.from({ length: n }, () => []); // not the parent: a cycle
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const seen = new Array<boolean>(n).fill(false);
for (let s = 0; s < n; s++) { // every part of the graph gets a search of its own
if (seen[s]) continue;
seen[s] = true;
const stack: [number, number][] = [[s, -1]];
while (stack.length) {
const [u, parent] = stack.pop()!;
for (const v of adj[u]) {
if (v === parent) continue;
if (seen[v]) return [u, v];
seen[v] = true;
stack.push([v, u]);
}
}
}
return null;
}
function show(n: number, edges: [number, number][]): void {
const found = closingEdge(n, edges);
const tree = edges.length === n - 1 && found === null; // a tree: n - 1 edges and no cycle
const cycle = found ? `cycle closed by ${found[0]}-${found[1]}` : "no cycle";
console.log(`${edges.map(([u, v]) => `${u}-${v}`).join(" ")}: ${cycle}${tree ? " | a tree" : " | not a tree"}`);
}
show(6, [[0, 1], [1, 2], [2, 0], [3, 4]]);
show(6, [[0, 1], [1, 2], [1, 3], [3, 4], [4, 5]]);
show(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5]]);
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treeusing System;
using System.Collections.Generic;
using System.Linq;
class Program {
static (int, int)? ClosingEdge(int n, (int u, int v)[] edges) { // a marked neighbour, not the parent: a cycle
var adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
foreach (var (u, v) in edges) {
adj[u].Add(v);
adj[v].Add(u);
}
var seen = new bool[n];
for (int s = 0; s < n; s++) { // every part of the graph gets a search of its own
if (seen[s]) continue;
seen[s] = true;
var stack = new Stack<(int u, int parent)>();
stack.Push((s, -1));
while (stack.Count > 0) {
var (u, parent) = stack.Pop();
foreach (int v in adj[u]) {
if (v == parent) continue;
if (seen[v]) return (u, v);
seen[v] = true;
stack.Push((v, u));
}
}
}
return null;
}
static void Show(int n, (int u, int v)[] edges) {
var found = ClosingEdge(n, edges);
bool tree = edges.Length == n - 1 && found == null; // a tree: n - 1 edges and no cycle
string cycle = found.HasValue ? $"cycle closed by {found.Value.Item1}-{found.Value.Item2}" : "no cycle";
Console.WriteLine($"{string.Join(" ", edges.Select(e => $"{e.u}-{e.v}"))}: {cycle}{(tree ? " | a tree" : " | not a tree")}");
}
static void Main() {
Show(6, new[] { (0, 1), (1, 2), (2, 0), (3, 4) });
Show(6, new[] { (0, 1), (1, 2), (1, 3), (3, 4), (4, 5) });
Show(6, new[] { (0, 1), (1, 2), (2, 0), (3, 4), (4, 5) });
}
}
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treepackage main
import (
"fmt"
"strings"
)
func closingEdge(n int, edges [][2]int) (int, int, bool) { // a marked neighbour, not the parent: a cycle
adj := make([][]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
adj[e[1]] = append(adj[e[1]], e[0])
}
seen := make([]bool, n)
for s := 0; s < n; s++ { // every part of the graph gets a search of its own
if seen[s] {
continue
}
seen[s] = true
stack := [][2]int{{s, -1}}
for len(stack) > 0 {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
u, parent := top[0], top[1]
for _, v := range adj[u] {
if v == parent {
continue
}
if seen[v] {
return u, v, true
}
seen[v] = true
stack = append(stack, [2]int{v, u})
}
}
}
return 0, 0, false
}
func show(n int, edges [][2]int) {
a, b, found := closingEdge(n, edges)
tree := len(edges) == n-1 && !found // a tree: n - 1 edges and no cycle
parts := []string{}
for _, e := range edges {
parts = append(parts, fmt.Sprintf("%d-%d", e[0], e[1]))
}
cycle := "no cycle"
if found {
cycle = fmt.Sprintf("cycle closed by %d-%d", a, b)
}
end := " | not a tree"
if tree {
end = " | a tree"
}
fmt.Printf("%s: %s%s\n", strings.Join(parts, " "), cycle, end)
}
func main() {
show(6, [][2]int{{0, 1}, {1, 2}, {2, 0}, {3, 4}})
show(6, [][2]int{{0, 1}, {1, 2}, {1, 3}, {3, 4}, {4, 5}})
show(6, [][2]int{{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}})
}
// 0-1 1-2 2-0 3-4: cycle closed by 2-1 | not a tree
// 0-1 1-2 1-3 3-4 4-5: no cycle | a tree
// 0-1 1-2 2-0 3-4 4-5: cycle closed by 2-1 | not a treeThe triangle 0, 1, 2 is closed by the edge 2-1: the search went from 0 to 1 and to 2, then found 1 marked from 2. A tree is a connected graph with no cycle, and with n vertices it has exactly n − 1 edges; with the edge count right, either fact gives the other. Graph Valid Tree is that check. The second graph has 5 edges for 6 vertices and no cycle: a tree. The third has 5 edges too, but the triangle spends one on a cycle, and the graph falls into two parts: not a tree.
With two edges between the same pair of vertices, compare edges, not vertices: the second edge back to the parent is a cycle of two. Union-Find and Minimum Spanning Trees finds cycles as the edges arrive, one at a time.
Cycles in directed graphs
In a directed graph, meeting a course again is no sign of a cycle, as the diamonds showed. A cycle is an edge back to a course on the path DFS is walking now, one it entered and hasn't finished. With three states the cycle is right there on the path: from that course to where the search stands, and back. For Course Schedule, with [course, needs] pairs:
import sys
sys.setrecursionlimit(10000)
def find_cycle(n, prerequisites): # Course Schedule: [course, needs]; an edge needs -> course
adj = [[] for _ in range(n)]
for course, need in prerequisites:
adj[need].append(course)
state, path = [0] * n, [] # 0 not seen, 1 on the current path, 2 finished
def dfs(u):
state[u] = 1
path.append(u)
for v in adj[u]:
if state[v] == 1: # back to a course on the path: the cycle is the path from v
return path[path.index(v):] + [v]
if state[v] == 0:
found = dfs(v)
if found:
return found
state[u] = 2
path.pop()
return None
for u in range(n):
if state[u] == 0:
found = dfs(u)
if found:
return found
return None
pre = [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4]]
for name, prerequisites in (("as given", pre), ("without [1, 3]", [p for p in pre if p != [1, 3]])):
cycle = find_cycle(6, prerequisites)
print(f"{name}: " + ("no, the cycle " + " -> ".join(map(str, cycle)) if cycle else "yes, all 6 courses"))
# as given: no, the cycle 1 -> 2 -> 3 -> 1
# without [1, 3]: yes, all 6 coursesimport java.util.*;
public class Main {
static List<List<Integer>> adj;
static int[] state; // 0 not seen, 1 on the current path, 2 finished
static List<Integer> path;
static List<Integer> dfs(int u) {
state[u] = 1;
path.add(u);
for (int v : adj.get(u)) {
if (state[v] == 1) { // back to a course on the path: the cycle is the path from v
List<Integer> cycle = new ArrayList<>(path.subList(path.indexOf(v), path.size()));
cycle.add(v);
return cycle;
}
if (state[v] == 0) {
List<Integer> found = dfs(v);
if (found != null) return found;
}
}
state[u] = 2;
path.remove(path.size() - 1);
return null;
}
static List<Integer> findCycle(int n, int[][] prerequisites) { // Course Schedule: [course, needs]
adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) adj.get(p[1]).add(p[0]); // an edge needs -> course
state = new int[n];
path = new ArrayList<>();
for (int u = 0; u < n; u++) {
if (state[u] == 0) {
List<Integer> found = dfs(u);
if (found != null) return found;
}
}
return null;
}
public static void main(String[] args) {
int[][] pre = {{1, 0}, {2, 1}, {3, 2}, {1, 3}, {4, 0}, {5, 4}};
int[][] without = {{1, 0}, {2, 1}, {3, 2}, {4, 0}, {5, 4}};
String[] names = {"as given", "without [1, 3]"};
int[][][] cases = {pre, without};
for (int i = 0; i < 2; i++) {
List<Integer> cycle = findCycle(6, cases[i]);
StringJoiner s = new StringJoiner(" -> ");
if (cycle != null) for (int v : cycle) s.add(String.valueOf(v));
System.out.println(names[i] + ": " + (cycle != null ? "no, the cycle " + s : "yes, all 6 courses"));
}
}
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 courses#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> state, path; // state: 0 not seen, 1 on the current path, 2 finished
vector<int> dfs(int u) {
state[u] = 1;
path.push_back(u);
for (int v : adj[u]) {
if (state[v] == 1) { // back to a course on the path: the cycle is the path from v
vector<int> cycle(find(path.begin(), path.end(), v), path.end());
cycle.push_back(v);
return cycle;
}
if (state[v] == 0) {
auto found = dfs(v);
if (!found.empty()) return found;
}
}
state[u] = 2;
path.pop_back();
return {};
}
vector<int> findCycle(int n, const vector<pair<int, int>>& prerequisites) { // Course Schedule: {course, needs}
adj.assign(n, {});
for (auto [course, need] : prerequisites) adj[need].push_back(course); // an edge needs -> course
state.assign(n, 0);
path.clear();
for (int u = 0; u < n; u++) {
if (state[u] == 0) {
auto found = dfs(u);
if (!found.empty()) return found;
}
}
return {};
}
int main() {
vector<pair<int, int>> pre = {{1, 0}, {2, 1}, {3, 2}, {1, 3}, {4, 0}, {5, 4}};
vector<pair<int, int>> without = {{1, 0}, {2, 1}, {3, 2}, {4, 0}, {5, 4}};
vector<pair<string, vector<pair<int, int>>>> cases = {{"as given", pre}, {"without [1, 3]", without}};
for (auto& [name, prerequisites] : cases) {
auto cycle = findCycle(6, prerequisites);
cout << name << ": ";
if (cycle.empty()) {
cout << "yes, all 6 courses\n";
continue;
}
cout << "no, the cycle";
for (size_t i = 0; i < cycle.size(); i++) cout << (i ? " -> " : " ") << cycle[i];
cout << "\n";
}
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 coursesfunction findCycle(n, prerequisites) { // Course Schedule: [course, needs]; an edge needs -> course
const adj = Array.from({ length: n }, () => []);
for (const [course, need] of prerequisites) adj[need].push(course);
const state = new Array(n).fill(0); // 0 not seen, 1 on the current path, 2 finished
const path = [];
const dfs = (u) => {
state[u] = 1;
path.push(u);
for (const v of adj[u]) {
if (state[v] === 1) return [...path.slice(path.indexOf(v)), v]; // back to a course on the path
if (state[v] === 0) {
const found = dfs(v);
if (found) return found;
}
}
state[u] = 2;
path.pop();
return null;
};
for (let u = 0; u < n; u++) {
if (state[u] === 0) {
const found = dfs(u);
if (found) return found;
}
}
return null;
}
const pre = [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4]];
const cases = [["as given", pre], ["without [1, 3]", pre.filter(([a, b]) => !(a === 1 && b === 3))]];
for (const [name, prerequisites] of cases) {
const cycle = findCycle(6, prerequisites);
console.log(`${name}: ${cycle ? `no, the cycle ${cycle.join(" -> ")}` : "yes, all 6 courses"}`);
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 coursesfunction findCycle(n: number, prerequisites: [number, number][]): number[] | null { // [course, needs]
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [course, need] of prerequisites) adj[need].push(course); // an edge needs -> course
const state = new Array<number>(n).fill(0); // 0 not seen, 1 on the current path, 2 finished
const path: number[] = [];
const dfs = (u: number): number[] | null => {
state[u] = 1;
path.push(u);
for (const v of adj[u]) {
if (state[v] === 1) return [...path.slice(path.indexOf(v)), v]; // back to a course on the path
if (state[v] === 0) {
const found = dfs(v);
if (found) return found;
}
}
state[u] = 2;
path.pop();
return null;
};
for (let u = 0; u < n; u++) {
if (state[u] === 0) {
const found = dfs(u);
if (found) return found;
}
}
return null;
}
const pre: [number, number][] = [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4]];
const cases: [string, [number, number][]][] = [["as given", pre],
["without [1, 3]", pre.filter(([a, b]) => !(a === 1 && b === 3))]];
for (const [name, prerequisites] of cases) {
const cycle = findCycle(6, prerequisites);
console.log(`${name}: ${cycle ? `no, the cycle ${cycle.join(" -> ")}` : "yes, all 6 courses"}`);
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 coursesusing System;
using System.Collections.Generic;
class Program {
static List<int>[] adj;
static int[] state; // 0 not seen, 1 on the current path, 2 finished
static List<int> path;
static List<int> Dfs(int u) {
state[u] = 1;
path.Add(u);
foreach (int v in adj[u]) {
if (state[v] == 1) { // back to a course on the path: the cycle is the path from v
int at = path.IndexOf(v);
var cycle = path.GetRange(at, path.Count - at);
cycle.Add(v);
return cycle;
}
if (state[v] == 0) {
var found = Dfs(v);
if (found != null) return found;
}
}
state[u] = 2;
path.RemoveAt(path.Count - 1);
return null;
}
static List<int> FindCycle(int n, int[][] prerequisites) { // Course Schedule: [course, needs]
adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
foreach (var p in prerequisites) adj[p[1]].Add(p[0]); // an edge needs -> course
state = new int[n];
path = new List<int>();
for (int u = 0; u < n; u++) {
if (state[u] == 0) {
var found = Dfs(u);
if (found != null) return found;
}
}
return null;
}
static void Main() {
int[][] pre = { new[] {1, 0}, new[] {2, 1}, new[] {3, 2}, new[] {1, 3}, new[] {4, 0}, new[] {5, 4} };
int[][] without = { new[] {1, 0}, new[] {2, 1}, new[] {3, 2}, new[] {4, 0}, new[] {5, 4} };
foreach (var (name, prerequisites) in new[] { ("as given", pre), ("without [1, 3]", without) }) {
var cycle = FindCycle(6, prerequisites);
Console.WriteLine($"{name}: " + (cycle != null ? "no, the cycle " + string.Join(" -> ", cycle) : "yes, all 6 courses"));
}
}
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 coursespackage main
import (
"fmt"
"strconv"
"strings"
)
var (
adj [][]int
state []int // 0 not seen, 1 on the current path, 2 finished
path []int
)
func dfs(u int) []int {
state[u] = 1
path = append(path, u)
for _, v := range adj[u] {
if state[v] == 1 { // back to a course on the path: the cycle is the path from v
at := 0
for path[at] != v {
at++
}
cycle := append(append([]int{}, path[at:]...), v)
return cycle
}
if state[v] == 0 {
if found := dfs(v); found != nil {
return found
}
}
}
state[u] = 2
path = path[:len(path)-1]
return nil
}
func findCycle(n int, prerequisites [][2]int) []int { // Course Schedule: {course, needs}
adj = make([][]int, n)
for _, p := range prerequisites {
adj[p[1]] = append(adj[p[1]], p[0]) // an edge needs -> course
}
state = make([]int, n)
path = nil
for u := 0; u < n; u++ {
if state[u] == 0 {
if found := dfs(u); found != nil {
return found
}
}
}
return nil
}
func main() {
pre := [][2]int{{1, 0}, {2, 1}, {3, 2}, {1, 3}, {4, 0}, {5, 4}}
without := [][2]int{{1, 0}, {2, 1}, {3, 2}, {4, 0}, {5, 4}}
names := []string{"as given", "without [1, 3]"}
for i, prerequisites := range [][][2]int{pre, without} {
cycle := findCycle(6, prerequisites)
if cycle == nil {
fmt.Printf("%s: yes, all 6 courses\n", names[i])
continue
}
parts := []string{}
for _, v := range cycle {
parts = append(parts, strconv.Itoa(v))
}
fmt.Printf("%s: no, the cycle %s\n", names[i], strings.Join(parts, " -> "))
}
}
// as given: no, the cycle 1 -> 2 -> 3 -> 1
// without [1, 3]: yes, all 6 coursesCourses 1, 2 and 3 wait on each other, so no order finishes all 6; take away the pair [1, 3] and every course can be done. Detect Cycle in Directed Graph is the same search, answering yes or no. An edge to a finished course is fine: everything past it was searched already, and none of it led back.
Two colours
A graph is bipartite when its vertices split into two groups with every edge between the groups, never inside one. Colour the start 0, everything it reaches 1, everything those reach 0, and so on, by BFS. An edge whose ends get the same colour means an odd cycle, which no two colours can cover; with no such edge, the colours are the split. Every part of the graph needs a start of its own:
from collections import deque
def two_colours(graph): # Is Graph Bipartite?: graph[u] lists u's neighbours
n = len(graph)
colour = [-1] * n
for s in range(n): # every part of the graph needs a start of its own
if colour[s] != -1:
continue
colour[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for v in graph[u]:
if colour[v] == -1:
colour[v] = 1 - colour[u] # the other colour from the one that reached it
queue.append(v)
elif colour[v] == colour[u]: # an edge inside one colour: an odd cycle
return None, (u, v)
return colour, None
for name, graph in (("a square and a pair", [[1, 3], [0, 2], [1, 3], [0, 2], [5], [4]]),
("a pentagon", [[1, 4], [0, 2], [1, 3], [2, 4], [3, 0]])):
colour, clash = two_colours(graph)
if colour:
print(f"{name}: bipartite, colours", " ".join(map(str, colour)))
else:
print(f"{name}: not bipartite, {clash[0]} and {clash[1]} share a colour")
# a square and a pair: bipartite, colours 0 1 0 1 0 1
# a pentagon: not bipartite, 2 and 3 share a colourimport java.util.*;
public class Main {
static int[] colour;
static int[] clash;
static boolean twoColours(int[][] graph) { // Is Graph Bipartite?: graph[u] lists u's neighbours
int n = graph.length;
colour = new int[n];
Arrays.fill(colour, -1);
for (int s = 0; s < n; s++) { // every part of the graph needs a start of its own
if (colour[s] != -1) continue;
colour[s] = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u]; // the other colour from the one that reached it
queue.add(v);
} else if (colour[v] == colour[u]) { // an edge inside one colour: an odd cycle
clash = new int[] {u, v};
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
String[] names = {"a square and a pair", "a pentagon"};
int[][][] graphs = {
{{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5}, {4}},
{{1, 4}, {0, 2}, {1, 3}, {2, 4}, {3, 0}},
};
for (int i = 0; i < 2; i++) {
if (twoColours(graphs[i])) {
StringJoiner s = new StringJoiner(" ");
for (int c : colour) s.add(String.valueOf(c));
System.out.println(names[i] + ": bipartite, colours " + s);
} else {
System.out.println(names[i] + ": not bipartite, " + clash[0] + " and " + clash[1] + " share a colour");
}
}
}
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colour#include <bits/stdc++.h>
using namespace std;
vector<int> colour;
pair<int, int> clash;
bool twoColours(const vector<vector<int>>& graph) { // Is Graph Bipartite?: graph[u] lists u's neighbours
int n = graph.size();
colour.assign(n, -1);
for (int s = 0; s < n; s++) { // every part of the graph needs a start of its own
if (colour[s] != -1) continue;
colour[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u]; // the other colour from the one that reached it
q.push(v);
} else if (colour[v] == colour[u]) { // an edge inside one colour: an odd cycle
clash = {u, v};
return false;
}
}
}
}
return true;
}
int main() {
vector<pair<string, vector<vector<int>>>> cases = {
{"a square and a pair", {{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5}, {4}}},
{"a pentagon", {{1, 4}, {0, 2}, {1, 3}, {2, 4}, {3, 0}}},
};
for (auto& [name, graph] : cases) {
if (twoColours(graph)) {
cout << name << ": bipartite, colours";
for (int c : colour) cout << " " << c;
cout << "\n";
} else {
cout << name << ": not bipartite, " << clash.first << " and " << clash.second << " share a colour\n";
}
}
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colourfunction twoColours(graph) { // Is Graph Bipartite?: graph[u] lists u's neighbours
const n = graph.length;
const colour = new Array(n).fill(-1);
for (let s = 0; s < n; s++) { // every part of the graph needs a start of its own
if (colour[s] !== -1) continue;
colour[s] = 0;
const queue = [s];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (colour[v] === -1) {
colour[v] = 1 - colour[u]; // the other colour from the one that reached it
queue.push(v);
} else if (colour[v] === colour[u]) { // an edge inside one colour: an odd cycle
return { colour: null, clash: [u, v] };
}
}
}
}
return { colour, clash: null };
}
const cases = [["a square and a pair", [[1, 3], [0, 2], [1, 3], [0, 2], [5], [4]]],
["a pentagon", [[1, 4], [0, 2], [1, 3], [2, 4], [3, 0]]]];
for (const [name, graph] of cases) {
const { colour, clash } = twoColours(graph);
console.log(colour ? `${name}: bipartite, colours ${colour.join(" ")}`
: `${name}: not bipartite, ${clash[0]} and ${clash[1]} share a colour`);
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colourfunction twoColours(graph: number[][]): { colour: number[] | null; clash: [number, number] | null } {
const n = graph.length; // Is Graph Bipartite?: graph[u] lists u's neighbours
const colour = new Array<number>(n).fill(-1);
for (let s = 0; s < n; s++) { // every part of the graph needs a start of its own
if (colour[s] !== -1) continue;
colour[s] = 0;
const queue = [s];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (colour[v] === -1) {
colour[v] = 1 - colour[u]; // the other colour from the one that reached it
queue.push(v);
} else if (colour[v] === colour[u]) { // an edge inside one colour: an odd cycle
return { colour: null, clash: [u, v] };
}
}
}
}
return { colour, clash: null };
}
const cases: [string, number[][]][] = [["a square and a pair", [[1, 3], [0, 2], [1, 3], [0, 2], [5], [4]]],
["a pentagon", [[1, 4], [0, 2], [1, 3], [2, 4], [3, 0]]]];
for (const [name, graph] of cases) {
const { colour, clash } = twoColours(graph);
console.log(colour ? `${name}: bipartite, colours ${colour.join(" ")}`
: `${name}: not bipartite, ${clash![0]} and ${clash![1]} share a colour`);
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colourusing System;
using System.Collections.Generic;
class Program {
static int[] colour;
static (int u, int v) clash;
static bool TwoColours(int[][] graph) { // Is Graph Bipartite?: graph[u] lists u's neighbours
int n = graph.Length;
colour = new int[n];
Array.Fill(colour, -1);
for (int s = 0; s < n; s++) { // every part of the graph needs a start of its own
if (colour[s] != -1) continue;
colour[s] = 0;
var queue = new Queue<int>();
queue.Enqueue(s);
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u]; // the other colour from the one that reached it
queue.Enqueue(v);
} else if (colour[v] == colour[u]) { // an edge inside one colour: an odd cycle
clash = (u, v);
return false;
}
}
}
}
return true;
}
static void Main() {
var cases = new (string name, int[][] graph)[] {
("a square and a pair", new[] { new[] {1, 3}, new[] {0, 2}, new[] {1, 3}, new[] {0, 2}, new[] {5}, new[] {4} }),
("a pentagon", new[] { new[] {1, 4}, new[] {0, 2}, new[] {1, 3}, new[] {2, 4}, new[] {3, 0} }),
};
foreach (var (name, graph) in cases) {
Console.WriteLine(TwoColours(graph) ? $"{name}: bipartite, colours {string.Join(" ", colour)}"
: $"{name}: not bipartite, {clash.u} and {clash.v} share a colour");
}
}
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colourpackage main
import (
"fmt"
"strconv"
"strings"
)
func twoColours(graph [][]int) ([]int, [2]int, bool) { // Is Graph Bipartite?: graph[u] lists u's neighbours
n := len(graph)
colour := make([]int, n)
for i := range colour {
colour[i] = -1
}
for s := 0; s < n; s++ { // every part of the graph needs a start of its own
if colour[s] != -1 {
continue
}
colour[s] = 0
queue := []int{s}
for head := 0; head < len(queue); head++ {
u := queue[head]
for _, v := range graph[u] {
if colour[v] == -1 {
colour[v] = 1 - colour[u] // the other colour from the one that reached it
queue = append(queue, v)
} else if colour[v] == colour[u] { // an edge inside one colour: an odd cycle
return nil, [2]int{u, v}, false
}
}
}
}
return colour, [2]int{}, true
}
func main() {
names := []string{"a square and a pair", "a pentagon"}
graphs := [][][]int{
{{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5}, {4}},
{{1, 4}, {0, 2}, {1, 3}, {2, 4}, {3, 0}},
}
for i, graph := range graphs {
colour, clash, ok := twoColours(graph)
if !ok {
fmt.Printf("%s: not bipartite, %d and %d share a colour\n", names[i], clash[0], clash[1])
continue
}
parts := []string{}
for _, c := range colour {
parts = append(parts, strconv.Itoa(c))
}
fmt.Printf("%s: bipartite, colours %s\n", names[i], strings.Join(parts, " "))
}
}
// a square and a pair: bipartite, colours 0 1 0 1 0 1
// a pentagon: not bipartite, 2 and 3 share a colourThe square takes 0 and 1 in turn, and the pair apart from it starts again at 0. Around the pentagon the colours meet at 2 and 3, both 0: five vertices in a ring can't alternate. Is Graph Bipartite? is exactly this.
Topological order from finishing times
A topological order lists the vertices so that every edge points forward: every course after the ones it needs. DFS gives one for free. A vertex finishes only after everything it leads to has finished, so in finishing order every edge points backward. Reverse it:
import sys
sys.setrecursionlimit(10000)
def finish_order(n, edges): # DFS: a vertex finishes after everything it leads to
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
seen, order = [False] * n, []
def dfs(u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
dfs(v)
order.append(u) # everything u leads to is in the list already
for u in range(n):
if not seen[u]:
dfs(u)
return order
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 4), (5, 6)]
finished = finish_order(7, edges)
topo = finished[::-1]
place = {v: i for i, v in enumerate(topo)}
print("finishing order:", " ".join(map(str, finished)))
print("reversed, a topological order:", " ".join(map(str, topo)))
print("every edge points forward:", "yes" if all(place[u] < place[v] for u, v in edges) else "no")
# finishing order: 4 3 1 2 0 6 5
# reversed, a topological order: 5 6 0 2 1 3 4
# every edge points forward: yesimport java.util.*;
public class Main {
static List<List<Integer>> adj;
static boolean[] seen;
static List<Integer> order;
static void dfs(int u) { // DFS: a vertex finishes after everything it leads to
seen[u] = true;
for (int v : adj.get(u)) if (!seen[v]) dfs(v);
order.add(u); // everything u leads to is in the list already
}
static List<Integer> finishOrder(int n, int[][] edges) {
adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(e[1]);
seen = new boolean[n];
order = new ArrayList<>();
for (int u = 0; u < n; u++) if (!seen[u]) dfs(u);
return order;
}
static String joined(List<Integer> xs) {
StringJoiner s = new StringJoiner(" ");
for (int x : xs) s.add(String.valueOf(x));
return s.toString();
}
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}};
List<Integer> finished = finishOrder(7, edges);
List<Integer> topo = new ArrayList<>(finished);
Collections.reverse(topo);
int[] place = new int[7];
for (int i = 0; i < 7; i++) place[topo.get(i)] = i;
boolean forward = true;
for (int[] e : edges) forward &= place[e[0]] < place[e[1]];
System.out.println("finishing order: " + joined(finished));
System.out.println("reversed, a topological order: " + joined(topo));
System.out.println("every edge points forward: " + (forward ? "yes" : "no"));
}
}
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yes#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<char> seen;
vector<int> order;
void dfs(int u) { // DFS: a vertex finishes after everything it leads to
seen[u] = 1;
for (int v : adj[u]) if (!seen[v]) dfs(v);
order.push_back(u); // everything u leads to is in the list already
}
vector<int> finishOrder(int n, const vector<pair<int, int>>& edges) {
adj.assign(n, {});
for (auto [u, v] : edges) adj[u].push_back(v);
seen.assign(n, 0);
order.clear();
for (int u = 0; u < n; u++) if (!seen[u]) dfs(u);
return order;
}
string joined(const vector<int>& xs) {
string s;
for (size_t i = 0; i < xs.size(); i++) s += (i ? " " : "") + to_string(xs[i]);
return s;
}
int main() {
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}};
auto finished = finishOrder(7, edges);
vector<int> topo(finished.rbegin(), finished.rend());
vector<int> place(7);
for (int i = 0; i < 7; i++) place[topo[i]] = i;
bool forward = all_of(edges.begin(), edges.end(), [&](auto e) { return place[e.first] < place[e.second]; });
cout << "finishing order: " << joined(finished) << "\n";
cout << "reversed, a topological order: " << joined(topo) << "\n";
cout << "every edge points forward: " << (forward ? "yes" : "no") << "\n";
}
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yesfunction finishOrder(n, edges) { // DFS: a vertex finishes after everything it leads to
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const seen = new Array(n).fill(false);
const order = [];
const dfs = (u) => {
seen[u] = true;
for (const v of adj[u]) if (!seen[v]) dfs(v);
order.push(u); // everything u leads to is in the list already
};
for (let u = 0; u < n; u++) if (!seen[u]) dfs(u);
return order;
}
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4], [5, 6]];
const finished = finishOrder(7, edges);
const topo = [...finished].reverse();
const place = new Map(topo.map((v, i) => [v, i]));
console.log(`finishing order: ${finished.join(" ")}`);
console.log(`reversed, a topological order: ${topo.join(" ")}`);
console.log(`every edge points forward: ${edges.every(([u, v]) => place.get(u) < place.get(v)) ? "yes" : "no"}`);
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yesfunction finishOrder(n: number, edges: [number, number][]): number[] { // a vertex finishes after
const adj: number[][] = Array.from({ length: n }, () => []); // everything it leads to
for (const [u, v] of edges) adj[u].push(v);
const seen = new Array<boolean>(n).fill(false);
const order: number[] = [];
const dfs = (u: number): void => {
seen[u] = true;
for (const v of adj[u]) if (!seen[v]) dfs(v);
order.push(u); // everything u leads to is in the list already
};
for (let u = 0; u < n; u++) if (!seen[u]) dfs(u);
return order;
}
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4], [5, 6]];
const finished = finishOrder(7, edges);
const topo = [...finished].reverse();
const place = new Map<number, number>(topo.map((v, i) => [v, i]));
console.log(`finishing order: ${finished.join(" ")}`);
console.log(`reversed, a topological order: ${topo.join(" ")}`);
console.log(`every edge points forward: ${edges.every(([u, v]) => place.get(u)! < place.get(v)!) ? "yes" : "no"}`);
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yesusing System;
using System.Collections.Generic;
using System.Linq;
class Program {
static List<int>[] adj;
static bool[] seen;
static List<int> order;
static void Dfs(int u) { // DFS: a vertex finishes after everything it leads to
seen[u] = true;
foreach (int v in adj[u]) if (!seen[v]) Dfs(v);
order.Add(u); // everything u leads to is in the list already
}
static List<int> FinishOrder(int n, (int u, int v)[] edges) {
adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
foreach (var (u, v) in edges) adj[u].Add(v);
seen = new bool[n];
order = new List<int>();
for (int u = 0; u < n; u++) if (!seen[u]) Dfs(u);
return order;
}
static void Main() {
var edges = new[] { (0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 4), (5, 6) };
var finished = FinishOrder(7, edges);
var topo = Enumerable.Reverse(finished).ToList();
var place = new int[7];
for (int i = 0; i < 7; i++) place[topo[i]] = i;
bool forward = edges.All(e => place[e.Item1] < place[e.Item2]);
Console.WriteLine($"finishing order: {string.Join(" ", finished)}");
Console.WriteLine($"reversed, a topological order: {string.Join(" ", topo)}");
Console.WriteLine($"every edge points forward: {(forward ? "yes" : "no")}");
}
}
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yespackage main
import (
"fmt"
"strconv"
"strings"
)
var (
adj [][]int
seen []bool
order []int
)
func dfs(u int) { // DFS: a vertex finishes after everything it leads to
seen[u] = true
for _, v := range adj[u] {
if !seen[v] {
dfs(v)
}
}
order = append(order, u) // everything u leads to is in the list already
}
func finishOrder(n int, edges [][2]int) []int {
adj = make([][]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
}
seen = make([]bool, n)
order = nil
for u := 0; u < n; u++ {
if !seen[u] {
dfs(u)
}
}
return order
}
func joined(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func main() {
edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}}
finished := finishOrder(7, edges)
topo := make([]int, len(finished))
for i, v := range finished {
topo[len(finished)-1-i] = v
}
place := make([]int, 7)
for i, v := range topo {
place[v] = i
}
forward := "yes"
for _, e := range edges {
if place[e[0]] >= place[e[1]] {
forward = "no"
}
}
fmt.Println("finishing order:", joined(finished))
fmt.Println("reversed, a topological order:", joined(topo))
fmt.Println("every edge points forward:", forward)
}
// finishing order: 4 3 1 2 0 6 5
// reversed, a topological order: 5 6 0 2 1 3 4
// every edge points forward: yes4 finishes first, because nothing comes after it, and 5 last. Reversed, 5 6 0 2 1 3 4 puts every edge forward. A graph with a cycle has no such order, so keep the three states as you go and stop at the first edge back to the path. Topological Sort asks for any one of these orders.
Kahn's algorithm: in-degrees
The other way builds the order from the front. A vertex with nothing pointing to it, an in-degree of 0, can go first. Take it and cross off its edges, and some of the vertices it pointed to have nothing pointing to them now either: put those in a queue and repeat. This is Kahn's algorithm, and it needs no recursion. Fewer than n vertices taken means a cycle: its vertices wait on each other for ever, and so does everything after them:
from collections import deque
def kahn(n, edges): # take what nothing points to, again and again
adj, indeg = [[] for _ in range(n)], [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
queue = deque(u for u in range(n) if indeg[u] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1 # one of v's prerequisites is done
if indeg[v] == 0:
queue.append(v)
stuck = [u for u in range(n) if indeg[u] > 0] # on a cycle, or after one
return order, stuck
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 4), (5, 6)]
for name, es in (("the 7 courses", edges), ("with 4 -> 1 added", edges + [(4, 1)])):
order, stuck = kahn(7, es)
print(f"{name}: order", " ".join(map(str, order)), "| stuck:", " ".join(map(str, stuck)) or "none")
# the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
# with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4import java.util.*;
public class Main {
static List<Integer> order, stuck;
static void kahn(int n, int[][] edges) { // take what nothing points to, again and again
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
indeg[e[1]]++;
}
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.add(u);
order = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : adj.get(u)) {
indeg[v]--; // one of v's prerequisites is done
if (indeg[v] == 0) queue.add(v);
}
}
stuck = new ArrayList<>();
for (int u = 0; u < n; u++) if (indeg[u] > 0) stuck.add(u); // on a cycle, or after one
}
static String joined(List<Integer> xs) {
StringJoiner s = new StringJoiner(" ");
for (int x : xs) s.add(String.valueOf(x));
return xs.isEmpty() ? "none" : s.toString();
}
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}};
int[][] withBack = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}, {4, 1}};
String[] names = {"the 7 courses", "with 4 -> 1 added"};
int[][][] cases = {edges, withBack};
for (int i = 0; i < 2; i++) {
kahn(7, cases[i]);
System.out.println(names[i] + ": order " + joined(order) + " | stuck: " + joined(stuck));
}
}
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4#include <bits/stdc++.h>
using namespace std;
pair<vector<int>, vector<int>> kahn(int n, const vector<pair<int, int>>& edges) { // take what nothing
vector<vector<int>> adj(n); // points to, again and again
vector<int> indeg(n, 0);
for (auto [u, v] : edges) {
adj[u].push_back(v);
indeg[v]++;
}
queue<int> q;
for (int u = 0; u < n; u++) if (indeg[u] == 0) q.push(u);
vector<int> order, stuck;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
indeg[v]--; // one of v's prerequisites is done
if (indeg[v] == 0) q.push(v);
}
}
for (int u = 0; u < n; u++) if (indeg[u] > 0) stuck.push_back(u); // on a cycle, or after one
return {order, stuck};
}
string joined(const vector<int>& xs) {
if (xs.empty()) return "none";
string s;
for (size_t i = 0; i < xs.size(); i++) s += (i ? " " : "") + to_string(xs[i]);
return s;
}
int main() {
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}};
auto withBack = edges;
withBack.push_back({4, 1});
vector<pair<string, vector<pair<int, int>>>> cases = {{"the 7 courses", edges}, {"with 4 -> 1 added", withBack}};
for (auto& [name, es] : cases) {
auto [order, stuck] = kahn(7, es);
cout << name << ": order " << joined(order) << " | stuck: " << joined(stuck) << "\n";
}
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4function kahn(n, edges) { // take what nothing points to, again and again
const adj = Array.from({ length: n }, () => []);
const indeg = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
indeg[v]++;
}
const queue = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u);
const order = [];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
order.push(u);
for (const v of adj[u]) {
indeg[v]--; // one of v's prerequisites is done
if (indeg[v] === 0) queue.push(v);
}
}
const stuck = [];
for (let u = 0; u < n; u++) if (indeg[u] > 0) stuck.push(u); // on a cycle, or after one
return { order, stuck };
}
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4], [5, 6]];
for (const [name, es] of [["the 7 courses", edges], ["with 4 -> 1 added", [...edges, [4, 1]]]]) {
const { order, stuck } = kahn(7, es);
console.log(`${name}: order ${order.join(" ")} | stuck: ${stuck.join(" ") || "none"}`);
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4function kahn(n: number, edges: [number, number][]): { order: number[]; stuck: number[] } {
const adj: number[][] = Array.from({ length: n }, () => []); // take what nothing points to, again and again
const indeg = new Array<number>(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
indeg[v]++;
}
const queue: number[] = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u);
const order: number[] = [];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
order.push(u);
for (const v of adj[u]) {
indeg[v]--; // one of v's prerequisites is done
if (indeg[v] === 0) queue.push(v);
}
}
const stuck: number[] = [];
for (let u = 0; u < n; u++) if (indeg[u] > 0) stuck.push(u); // on a cycle, or after one
return { order, stuck };
}
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [5, 4], [5, 6]];
const cases: [string, [number, number][]][] = [["the 7 courses", edges], ["with 4 -> 1 added", [...edges, [4, 1]]]];
for (const [name, es] of cases) {
const { order, stuck } = kahn(7, es);
console.log(`${name}: order ${order.join(" ")} | stuck: ${stuck.join(" ") || "none"}`);
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static (List<int> order, List<int> stuck) Kahn(int n, (int u, int v)[] edges) { // take what nothing points
var adj = new List<int>[n]; // to, again and again
for (int i = 0; i < n; i++) adj[i] = new List<int>();
var indeg = new int[n];
foreach (var (u, v) in edges) {
adj[u].Add(v);
indeg[v]++;
}
var queue = new Queue<int>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.Enqueue(u);
var order = new List<int>();
while (queue.Count > 0) {
int u = queue.Dequeue();
order.Add(u);
foreach (int v in adj[u]) {
indeg[v]--; // one of v's prerequisites is done
if (indeg[v] == 0) queue.Enqueue(v);
}
}
var stuck = Enumerable.Range(0, n).Where(u => indeg[u] > 0).ToList(); // on a cycle, or after one
return (order, stuck);
}
static string Joined(List<int> xs) => xs.Count == 0 ? "none" : string.Join(" ", xs);
static void Main() {
var edges = new[] { (0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 4), (5, 6) };
var withBack = edges.Append((4, 1)).ToArray();
foreach (var (name, es) in new[] { ("the 7 courses", edges), ("with 4 -> 1 added", withBack) }) {
var (order, stuck) = Kahn(7, es);
Console.WriteLine($"{name}: order {Joined(order)} | stuck: {Joined(stuck)}");
}
}
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4package main
import (
"fmt"
"strconv"
"strings"
)
func kahn(n int, edges [][2]int) ([]int, []int) { // take what nothing points to, again and again
adj := make([][]int, n)
indeg := make([]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
indeg[e[1]]++
}
queue := []int{}
for u := 0; u < n; u++ {
if indeg[u] == 0 {
queue = append(queue, u)
}
}
order := []int{}
for head := 0; head < len(queue); head++ {
u := queue[head]
order = append(order, u)
for _, v := range adj[u] {
indeg[v]-- // one of v's prerequisites is done
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
stuck := []int{}
for u := 0; u < n; u++ {
if indeg[u] > 0 { // on a cycle, or after one
stuck = append(stuck, u)
}
}
return order, stuck
}
func joined(xs []int) string {
if len(xs) == 0 {
return "none"
}
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func main() {
edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 4}, {5, 6}}
withBack := append(append([][2]int{}, edges...), [2]int{4, 1})
names := []string{"the 7 courses", "with 4 -> 1 added"}
for i, es := range [][][2]int{edges, withBack} {
order, stuck := kahn(7, es)
fmt.Printf("%s: order %s | stuck: %s\n", names[i], joined(order), joined(stuck))
}
}
// the 7 courses: order 0 5 1 2 6 3 4 | stuck: none
// with 4 -> 1 added: order 0 5 2 6 | stuck: 1 3 4All 7 come out, in another order than the DFS one and just as good: 0 and 5 first, the two with nothing before them. Add 4 → 1 and the queue runs dry after 0, 5, 2 and 6, with 1, 3 and 4 still waiting on one another, the cycle 1 → 3 → 4 → 1. Course Schedule II returns the order, or an empty list when anything is left waiting; Kahn's Algorithm (BFS Topo Sort) asks for the order alone.
Kahn's Queue. Run it yourself: take a course with nothing before it, watch the in-degrees drop, and see which courses a cycle leaves stuck.
What comes before what
Course Schedule IV asks, for pairs of courses, whether one must come before the other at all, directly or through others. Walk the courses in topological order, keeping for each one the set of everything before it. When a course comes off the queue its set is complete, so pass it on, with the course itself, to everything it points to. With at most 100 courses, a row of booleans per course does:
from collections import deque
def answer_queries(n, prerequisites, queries): # Course Schedule IV: is a a prerequisite of b, directly or not?
adj, indeg = [[] for _ in range(n)], [0] * n
for a, b in prerequisites: # [a, b]: a must come before b
adj[a].append(b)
indeg[b] += 1
before = [[False] * n for _ in range(n)] # before[v][u]: u comes before v
queue = deque(u for u in range(n) if indeg[u] == 0)
while queue: # in topological order: u's row is complete when it comes off
u = queue.popleft()
for v in adj[u]:
before[v][u] = True
for k in range(n):
before[v][k] = before[v][k] or before[u][k]
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)
return [before[b][a] for a, b in queries]
queries = [[0, 3], [3, 0], [4, 2], [0, 5]]
answers = answer_queries(6, [[0, 1], [1, 2], [2, 3], [0, 4], [4, 5]], queries)
print(" | ".join(f"{a} before {b}: {'yes' if x else 'no'}" for (a, b), x in zip(queries, answers)))
# 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yesimport java.util.*;
public class Main {
static boolean[] answerQueries(int n, int[][] prerequisites, int[][] queries) { // is a before b, at all?
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] p : prerequisites) { // [a, b]: a must come before b
adj.get(p[0]).add(p[1]);
indeg[p[1]]++;
}
boolean[][] before = new boolean[n][n]; // before[v][u]: u comes before v
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.add(u);
while (!queue.isEmpty()) { // in topological order: u's row is complete when it comes off
int u = queue.poll();
for (int v : adj.get(u)) {
before[v][u] = true;
for (int k = 0; k < n; k++) before[v][k] = before[v][k] || before[u][k];
if (--indeg[v] == 0) queue.add(v);
}
}
boolean[] out = new boolean[queries.length];
for (int i = 0; i < queries.length; i++) out[i] = before[queries[i][1]][queries[i][0]];
return out;
}
public static void main(String[] args) {
int[][] queries = {{0, 3}, {3, 0}, {4, 2}, {0, 5}};
boolean[] answers = answerQueries(6, new int[][] {{0, 1}, {1, 2}, {2, 3}, {0, 4}, {4, 5}}, queries);
StringJoiner s = new StringJoiner(" | ");
for (int i = 0; i < queries.length; i++)
s.add(queries[i][0] + " before " + queries[i][1] + ": " + (answers[i] ? "yes" : "no"));
System.out.println(s);
}
}
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yes#include <bits/stdc++.h>
using namespace std;
vector<bool> answerQueries(int n, const vector<pair<int, int>>& prerequisites,
const vector<pair<int, int>>& queries) { // Course Schedule IV: is a before b, at all?
vector<vector<int>> adj(n);
vector<int> indeg(n, 0);
for (auto [a, b] : prerequisites) { // {a, b}: a must come before b
adj[a].push_back(b);
indeg[b]++;
}
vector<vector<bool>> before(n, vector<bool>(n, false)); // before[v][u]: u comes before v
queue<int> q;
for (int u = 0; u < n; u++) if (indeg[u] == 0) q.push(u);
while (!q.empty()) { // in topological order: u's row is complete when it comes off
int u = q.front();
q.pop();
for (int v : adj[u]) {
before[v][u] = true;
for (int k = 0; k < n; k++) before[v][k] = before[v][k] || before[u][k];
if (--indeg[v] == 0) q.push(v);
}
}
vector<bool> out;
for (auto [a, b] : queries) out.push_back(before[b][a]);
return out;
}
int main() {
vector<pair<int, int>> queries = {{0, 3}, {3, 0}, {4, 2}, {0, 5}};
auto answers = answerQueries(6, {{0, 1}, {1, 2}, {2, 3}, {0, 4}, {4, 5}}, queries);
for (size_t i = 0; i < queries.size(); i++)
cout << (i ? " | " : "") << queries[i].first << " before " << queries[i].second << ": "
<< (answers[i] ? "yes" : "no");
cout << "\n";
}
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yesfunction answerQueries(n, prerequisites, queries) { // Course Schedule IV: is a a prerequisite of b, at all?
const adj = Array.from({ length: n }, () => []);
const indeg = new Array(n).fill(0);
for (const [a, b] of prerequisites) { // [a, b]: a must come before b
adj[a].push(b);
indeg[b]++;
}
const before = Array.from({ length: n }, () => new Array(n).fill(false)); // before[v][u]: u before v
const queue = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u);
for (let head = 0; head < queue.length; head++) { // in topological order: u's row is complete when it comes off
const u = queue[head];
for (const v of adj[u]) {
before[v][u] = true;
for (let k = 0; k < n; k++) before[v][k] = before[v][k] || before[u][k];
if (--indeg[v] === 0) queue.push(v);
}
}
return queries.map(([a, b]) => before[b][a]);
}
const queries = [[0, 3], [3, 0], [4, 2], [0, 5]];
const answers = answerQueries(6, [[0, 1], [1, 2], [2, 3], [0, 4], [4, 5]], queries);
console.log(queries.map(([a, b], i) => `${a} before ${b}: ${answers[i] ? "yes" : "no"}`).join(" | "));
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yesfunction answerQueries(n: number, prerequisites: [number, number][], queries: [number, number][]): boolean[] {
const adj: number[][] = Array.from({ length: n }, () => []); // Course Schedule IV: is a before b, at all?
const indeg = new Array<number>(n).fill(0);
for (const [a, b] of prerequisites) { // [a, b]: a must come before b
adj[a].push(b);
indeg[b]++;
}
const before: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false)); // u before v
const queue: number[] = [];
for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u);
for (let head = 0; head < queue.length; head++) { // in topological order: u's row is complete when it comes off
const u = queue[head];
for (const v of adj[u]) {
before[v][u] = true;
for (let k = 0; k < n; k++) before[v][k] = before[v][k] || before[u][k];
if (--indeg[v] === 0) queue.push(v);
}
}
return queries.map(([a, b]) => before[b][a]);
}
const queries: [number, number][] = [[0, 3], [3, 0], [4, 2], [0, 5]];
const answers = answerQueries(6, [[0, 1], [1, 2], [2, 3], [0, 4], [4, 5]], queries);
console.log(queries.map(([a, b], i) => `${a} before ${b}: ${answers[i] ? "yes" : "no"}`).join(" | "));
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yesusing System;
using System.Collections.Generic;
using System.Linq;
class Program {
static bool[] AnswerQueries(int n, (int a, int b)[] prerequisites, (int a, int b)[] queries) { // a before b?
var adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
var indeg = new int[n];
foreach (var (a, b) in prerequisites) { // (a, b): a must come before b
adj[a].Add(b);
indeg[b]++;
}
var before = new bool[n, n]; // before[v, u]: u comes before v
var queue = new Queue<int>();
for (int u = 0; u < n; u++) if (indeg[u] == 0) queue.Enqueue(u);
while (queue.Count > 0) { // in topological order: u's row is complete when it comes off
int u = queue.Dequeue();
foreach (int v in adj[u]) {
before[v, u] = true;
for (int k = 0; k < n; k++) before[v, k] = before[v, k] || before[u, k];
if (--indeg[v] == 0) queue.Enqueue(v);
}
}
return queries.Select(q => before[q.b, q.a]).ToArray();
}
static void Main() {
var queries = new[] { (0, 3), (3, 0), (4, 2), (0, 5) };
var answers = AnswerQueries(6, new[] { (0, 1), (1, 2), (2, 3), (0, 4), (4, 5) }, queries);
Console.WriteLine(string.Join(" | ", queries.Select((q, i) => $"{q.Item1} before {q.Item2}: {(answers[i] ? "yes" : "no")}")));
}
}
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yespackage main
import (
"fmt"
"strings"
)
func answerQueries(n int, prerequisites, queries [][2]int) []bool { // Course Schedule IV: is a before b, at all?
adj := make([][]int, n)
indeg := make([]int, n)
for _, p := range prerequisites { // {a, b}: a must come before b
adj[p[0]] = append(adj[p[0]], p[1])
indeg[p[1]]++
}
before := make([][]bool, n) // before[v][u]: u comes before v
for i := range before {
before[i] = make([]bool, n)
}
queue := []int{}
for u := 0; u < n; u++ {
if indeg[u] == 0 {
queue = append(queue, u)
}
}
for head := 0; head < len(queue); head++ { // in topological order: u's row is complete when it comes off
u := queue[head]
for _, v := range adj[u] {
before[v][u] = true
for k := 0; k < n; k++ {
before[v][k] = before[v][k] || before[u][k]
}
indeg[v]--
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
out := make([]bool, len(queries))
for i, q := range queries {
out[i] = before[q[1]][q[0]]
}
return out
}
func main() {
queries := [][2]int{{0, 3}, {3, 0}, {4, 2}, {0, 5}}
answers := answerQueries(6, [][2]int{{0, 1}, {1, 2}, {2, 3}, {0, 4}, {4, 5}}, queries)
parts := []string{}
for i, q := range queries {
word := "no"
if answers[i] {
word = "yes"
}
parts = append(parts, fmt.Sprintf("%d before %d: %s", q[0], q[1], word))
}
fmt.Println(strings.Join(parts, " | "))
}
// 0 before 3: yes | 3 before 0: no | 4 before 2: no | 0 before 5: yes0 comes before 3 through 1 and 2, and before 5 through 4; 4 and 2 sit on different branches, so neither comes before the other. Each edge copies one row of n, so the whole walk is O(n × E).
Safe states
Find Eventual Safe States calls a vertex safe when every path from it ends at a dead end, a vertex with no way out. It's unsafe exactly when some path from it reaches a cycle. The three states answer this too: a vertex that finishes without meeting the path again is safe, and one that meets it stays marked as on a path, unsafe, with every vertex on the way to it:
import sys
sys.setrecursionlimit(10000)
def safe_states(graph): # Find Eventual Safe States: graph[u] lists where u leads
n = len(graph)
state = [0] * n # 0 not seen, 1 on a path or found unsafe, 2 safe
def safe(u):
if state[u]:
return state[u] == 2
state[u] = 1
for v in graph[u]:
if not safe(v):
return False # a cycle on this path or ahead of it: u stays 1, unsafe
state[u] = 2 # every way out of u ends at a dead end
return True
return [u for u in range(n) if safe(u)]
graph = [[1], [2], [0, 3], [4], [], [4, 6], [5], [3], [0]]
good = safe_states(graph)
print("safe:", " ".join(map(str, good)), "| not safe:", " ".join(str(u) for u in range(len(graph)) if u not in good))
# safe: 3 4 7 | not safe: 0 1 2 5 6 8import java.util.*;
public class Main {
static int[][] graph;
static int[] state; // 0 not seen, 1 on a path or found unsafe, 2 safe
static boolean safe(int u) { // Find Eventual Safe States: graph[u] lists where u leads
if (state[u] != 0) return state[u] == 2;
state[u] = 1;
for (int v : graph[u]) if (!safe(v)) return false; // a cycle on this path or ahead of it: u stays 1
state[u] = 2; // every way out of u ends at a dead end
return true;
}
public static void main(String[] args) {
graph = new int[][] {{1}, {2}, {0, 3}, {4}, {}, {4, 6}, {5}, {3}, {0}};
state = new int[graph.length];
StringJoiner good = new StringJoiner(" "), bad = new StringJoiner(" ");
for (int u = 0; u < graph.length; u++) (safe(u) ? good : bad).add(String.valueOf(u));
System.out.println("safe: " + good + " | not safe: " + bad);
}
}
// safe: 3 4 7 | not safe: 0 1 2 5 6 8#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<int> state; // 0 not seen, 1 on a path or found unsafe, 2 safe
bool safe(int u) { // Find Eventual Safe States: graph[u] lists where u leads
if (state[u]) return state[u] == 2;
state[u] = 1;
for (int v : graph[u]) if (!safe(v)) return false; // a cycle on this path or ahead of it: u stays 1
state[u] = 2; // every way out of u ends at a dead end
return true;
}
int main() {
graph = {{1}, {2}, {0, 3}, {4}, {}, {4, 6}, {5}, {3}, {0}};
state.assign(graph.size(), 0);
string good, bad;
for (int u = 0; u < (int) graph.size(); u++) {
string& s = safe(u) ? good : bad;
s += (s.empty() ? "" : " ") + to_string(u);
}
cout << "safe: " << good << " | not safe: " << bad << "\n";
}
// safe: 3 4 7 | not safe: 0 1 2 5 6 8function safeStates(graph) { // Find Eventual Safe States: graph[u] lists where u leads
const state = new Array(graph.length).fill(0); // 0 not seen, 1 on a path or found unsafe, 2 safe
const safe = (u) => {
if (state[u]) return state[u] === 2;
state[u] = 1;
for (const v of graph[u]) if (!safe(v)) return false; // a cycle on this path or ahead of it: u stays 1
state[u] = 2; // every way out of u ends at a dead end
return true;
};
return graph.map((_, u) => safe(u));
}
const graph = [[1], [2], [0, 3], [4], [], [4, 6], [5], [3], [0]];
const isSafe = safeStates(graph);
const all = graph.map((_, u) => u);
console.log(`safe: ${all.filter((u) => isSafe[u]).join(" ")} | not safe: ${all.filter((u) => !isSafe[u]).join(" ")}`);
// safe: 3 4 7 | not safe: 0 1 2 5 6 8function safeStates(graph: number[][]): boolean[] { // Find Eventual Safe States: graph[u] lists where u leads
const state = new Array<number>(graph.length).fill(0); // 0 not seen, 1 on a path or found unsafe, 2 safe
const safe = (u: number): boolean => {
if (state[u]) return state[u] === 2;
state[u] = 1;
for (const v of graph[u]) if (!safe(v)) return false; // a cycle on this path or ahead of it: u stays 1
state[u] = 2; // every way out of u ends at a dead end
return true;
};
return graph.map((_, u) => safe(u));
}
const graph: number[][] = [[1], [2], [0, 3], [4], [], [4, 6], [5], [3], [0]];
const isSafe = safeStates(graph);
const all = graph.map((_, u) => u);
console.log(`safe: ${all.filter((u) => isSafe[u]).join(" ")} | not safe: ${all.filter((u) => !isSafe[u]).join(" ")}`);
// safe: 3 4 7 | not safe: 0 1 2 5 6 8using System;
using System.Collections.Generic;
class Program {
static int[][] graph;
static int[] state; // 0 not seen, 1 on a path or found unsafe, 2 safe
static bool Safe(int u) { // Find Eventual Safe States: graph[u] lists where u leads
if (state[u] != 0) return state[u] == 2;
state[u] = 1;
foreach (int v in graph[u]) if (!Safe(v)) return false; // a cycle on this path or ahead of it: u stays 1
state[u] = 2; // every way out of u ends at a dead end
return true;
}
static void Main() {
graph = new[] { new[] {1}, new[] {2}, new[] {0, 3}, new[] {4}, new int[0], new[] {4, 6}, new[] {5}, new[] {3}, new[] {0} };
state = new int[graph.Length];
var good = new List<int>();
var bad = new List<int>();
for (int u = 0; u < graph.Length; u++) (Safe(u) ? good : bad).Add(u);
Console.WriteLine($"safe: {string.Join(" ", good)} | not safe: {string.Join(" ", bad)}");
}
}
// safe: 3 4 7 | not safe: 0 1 2 5 6 8package main
import (
"fmt"
"strconv"
"strings"
)
var (
graph [][]int
state []int // 0 not seen, 1 on a path or found unsafe, 2 safe
)
func safe(u int) bool { // Find Eventual Safe States: graph[u] lists where u leads
if state[u] != 0 {
return state[u] == 2
}
state[u] = 1
for _, v := range graph[u] {
if !safe(v) {
return false // a cycle on this path or ahead of it: u stays 1, unsafe
}
}
state[u] = 2 // every way out of u ends at a dead end
return true
}
func main() {
graph = [][]int{{1}, {2}, {0, 3}, {4}, {}, {4, 6}, {5}, {3}, {0}}
state = make([]int, len(graph))
good, bad := []string{}, []string{}
for u := range graph {
if safe(u) {
good = append(good, strconv.Itoa(u))
} else {
bad = append(bad, strconv.Itoa(u))
}
}
fmt.Printf("safe: %s | not safe: %s\n", strings.Join(good, " "), strings.Join(bad, " "))
}
// safe: 3 4 7 | not safe: 0 1 2 5 6 80, 1 and 2 form a cycle, and so do 5 and 6; 8 leads into the first one. 3 ends at 4, a dead end, and 7 leads to 3, so 3, 4 and 7 are safe. Kahn's algorithm gives the same answer on the reversed edges, starting from the dead ends.
Peeling leaves to the centre
Minimum Height Trees asks which roots make a tree as short as it can be. Peel it like an onion: remove every leaf, then every vertex that has become a leaf, and so on, until one or two are left. They're the middle of the tree's longest path, and the best roots:
def centres(n, edges): # Minimum Height Trees: peel the leaves until one or two are left
if n == 1:
return [0], []
adj, degree = [[] for _ in range(n)], [0] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
degree[u] += 1
degree[v] += 1
leaves = [u for u in range(n) if degree[u] == 1]
left, peeled = n, []
while left > 2:
peeled.append(leaves)
left -= len(leaves)
nxt = []
for leaf in leaves:
for v in adj[leaf]:
degree[v] -= 1
if degree[v] == 1: # v has just become a leaf
nxt.append(v)
leaves = nxt
return sorted(leaves), peeled
roots, peeled = centres(9, [(0, 1), (1, 2), (2, 3), (3, 4), (2, 5), (5, 6), (3, 7), (7, 8)])
for k, layer in enumerate(peeled, 1):
print(f"peel {k}:", " ".join(map(str, layer)))
print("the roots of the shortest trees:", " ".join(map(str, roots)))
# peel 1: 0 4 6 8
# peel 2: 1 5 7
# the roots of the shortest trees: 2 3import java.util.*;
public class Main {
static List<List<Integer>> peeled = new ArrayList<>();
static List<Integer> centres(int n, int[][] edges) { // Minimum Height Trees: peel the leaves to one or two
if (n == 1) return List.of(0);
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] degree = new int[n];
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
List<Integer> leaves = new ArrayList<>();
for (int u = 0; u < n; u++) if (degree[u] == 1) leaves.add(u);
int left = n;
while (left > 2) {
peeled.add(leaves);
left -= leaves.size();
List<Integer> next = new ArrayList<>();
for (int leaf : leaves) {
for (int v : adj.get(leaf)) {
if (--degree[v] == 1) next.add(v); // v has just become a leaf
}
}
leaves = next;
}
Collections.sort(leaves);
return leaves;
}
static String joined(List<Integer> xs) {
StringJoiner s = new StringJoiner(" ");
for (int x : xs) s.add(String.valueOf(x));
return s.toString();
}
public static void main(String[] args) {
List<Integer> roots = centres(9, new int[][] {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {2, 5}, {5, 6}, {3, 7}, {7, 8}});
for (int k = 0; k < peeled.size(); k++) System.out.println("peel " + (k + 1) + ": " + joined(peeled.get(k)));
System.out.println("the roots of the shortest trees: " + joined(roots));
}
}
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> peeled;
vector<int> centres(int n, const vector<pair<int, int>>& edges) { // Minimum Height Trees: peel the leaves until
if (n == 1) return {0}; // one or two are left
vector<vector<int>> adj(n);
vector<int> degree(n, 0);
for (auto [u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
degree[u]++;
degree[v]++;
}
vector<int> leaves;
for (int u = 0; u < n; u++) if (degree[u] == 1) leaves.push_back(u);
int left = n;
while (left > 2) {
peeled.push_back(leaves);
left -= leaves.size();
vector<int> next;
for (int leaf : leaves)
for (int v : adj[leaf])
if (--degree[v] == 1) next.push_back(v); // v has just become a leaf
leaves = next;
}
sort(leaves.begin(), leaves.end());
return leaves;
}
string joined(const vector<int>& xs) {
string s;
for (size_t i = 0; i < xs.size(); i++) s += (i ? " " : "") + to_string(xs[i]);
return s;
}
int main() {
auto roots = centres(9, {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {2, 5}, {5, 6}, {3, 7}, {7, 8}});
for (size_t k = 0; k < peeled.size(); k++) cout << "peel " << k + 1 << ": " << joined(peeled[k]) << "\n";
cout << "the roots of the shortest trees: " << joined(roots) << "\n";
}
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3function centres(n, edges) { // Minimum Height Trees: peel the leaves until one or two are left
if (n === 1) return { roots: [0], peeled: [] };
const adj = Array.from({ length: n }, () => []);
const degree = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
degree[u]++;
degree[v]++;
}
let leaves = [];
for (let u = 0; u < n; u++) if (degree[u] === 1) leaves.push(u);
let left = n;
const peeled = [];
while (left > 2) {
peeled.push(leaves);
left -= leaves.length;
const next = [];
for (const leaf of leaves)
for (const v of adj[leaf])
if (--degree[v] === 1) next.push(v); // v has just become a leaf
leaves = next;
}
return { roots: leaves.sort((a, b) => a - b), peeled };
}
const { roots, peeled } = centres(9, [[0, 1], [1, 2], [2, 3], [3, 4], [2, 5], [5, 6], [3, 7], [7, 8]]);
peeled.forEach((layer, k) => console.log(`peel ${k + 1}: ${layer.join(" ")}`));
console.log(`the roots of the shortest trees: ${roots.join(" ")}`);
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3function centres(n: number, edges: [number, number][]): { roots: number[]; peeled: number[][] } {
if (n === 1) return { roots: [0], peeled: [] }; // Minimum Height Trees: peel the leaves to one or two
const adj: number[][] = Array.from({ length: n }, () => []);
const degree = new Array<number>(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
degree[u]++;
degree[v]++;
}
let leaves: number[] = [];
for (let u = 0; u < n; u++) if (degree[u] === 1) leaves.push(u);
let left = n;
const peeled: number[][] = [];
while (left > 2) {
peeled.push(leaves);
left -= leaves.length;
const next: number[] = [];
for (const leaf of leaves)
for (const v of adj[leaf])
if (--degree[v] === 1) next.push(v); // v has just become a leaf
leaves = next;
}
return { roots: leaves.sort((a, b) => a - b), peeled };
}
const { roots, peeled } = centres(9, [[0, 1], [1, 2], [2, 3], [3, 4], [2, 5], [5, 6], [3, 7], [7, 8]]);
peeled.forEach((layer, k) => console.log(`peel ${k + 1}: ${layer.join(" ")}`));
console.log(`the roots of the shortest trees: ${roots.join(" ")}`);
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3using System;
using System.Collections.Generic;
class Program {
static List<List<int>> peeled = new List<List<int>>();
static List<int> Centres(int n, (int u, int v)[] edges) { // Minimum Height Trees: peel the leaves to one or two
if (n == 1) return new List<int> { 0 };
var adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>();
var degree = new int[n];
foreach (var (u, v) in edges) {
adj[u].Add(v);
adj[v].Add(u);
degree[u]++;
degree[v]++;
}
var leaves = new List<int>();
for (int u = 0; u < n; u++) if (degree[u] == 1) leaves.Add(u);
int left = n;
while (left > 2) {
peeled.Add(leaves);
left -= leaves.Count;
var next = new List<int>();
foreach (int leaf in leaves)
foreach (int v in adj[leaf])
if (--degree[v] == 1) next.Add(v); // v has just become a leaf
leaves = next;
}
leaves.Sort();
return leaves;
}
static void Main() {
var roots = Centres(9, new[] { (0, 1), (1, 2), (2, 3), (3, 4), (2, 5), (5, 6), (3, 7), (7, 8) });
for (int k = 0; k < peeled.Count; k++) Console.WriteLine($"peel {k + 1}: {string.Join(" ", peeled[k])}");
Console.WriteLine($"the roots of the shortest trees: {string.Join(" ", roots)}");
}
}
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func centres(n int, edges [][2]int) ([]int, [][]int) { // Minimum Height Trees: peel the leaves to one or two
if n == 1 {
return []int{0}, nil
}
adj := make([][]int, n)
degree := make([]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
adj[e[1]] = append(adj[e[1]], e[0])
degree[e[0]]++
degree[e[1]]++
}
leaves := []int{}
for u := 0; u < n; u++ {
if degree[u] == 1 {
leaves = append(leaves, u)
}
}
left, peeled := n, [][]int{}
for left > 2 {
peeled = append(peeled, leaves)
left -= len(leaves)
next := []int{}
for _, leaf := range leaves {
for _, v := range adj[leaf] {
degree[v]--
if degree[v] == 1 { // v has just become a leaf
next = append(next, v)
}
}
}
leaves = next
}
sort.Ints(leaves)
return leaves, peeled
}
func joined(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = strconv.Itoa(x)
}
return strings.Join(parts, " ")
}
func main() {
roots, peeled := centres(9, [][2]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {2, 5}, {5, 6}, {3, 7}, {7, 8}})
for k, layer := range peeled {
fmt.Printf("peel %d: %s\n", k+1, joined(layer))
}
fmt.Println("the roots of the shortest trees:", joined(roots))
}
// peel 1: 0 4 6 8
// peel 2: 1 5 7
// the roots of the shortest trees: 2 3Two peels, 0, 4, 6 and 8, then 1, 5 and 7, leave 2 and 3. A BFS from every vertex would find the same two for about n times the work.
Letters from sorted words
Alien Dictionary hands over words sorted in an unknown alphabet and asks for the alphabet. Two neighbouring words agree up to their first different letter, and there the first word's letter comes before the second's: an edge. Nothing else in the pair says anything. Then any topological order of the letters is an answer. A word followed by its own prefix, dcab before dca, can't be sorted by any alphabet, so the answer is empty, and so it is when the letters' edges hold a cycle:
from collections import deque
def alien_order(words): # Alien Dictionary: the letters' order, from words already sorted
present = sorted(set("".join(words)))
edge = [[False] * 26 for _ in range(26)]
indeg = [0] * 26
for a, b in zip(words, words[1:]): # each pair of neighbouring words gives one rule at most
for x, y in zip(a, b):
if x != y: # the first letters that differ: x comes before y
i, j = ord(x) - 97, ord(y) - 97
if not edge[i][j]:
edge[i][j] = True
indeg[j] += 1
break
else:
if len(a) > len(b): # a word before its own prefix: no order allows that
return ""
queue = deque(ord(c) - 97 for c in present if indeg[ord(c) - 97] == 0)
order = []
while queue:
i = queue.popleft()
order.append(chr(97 + i))
for j in range(26):
if edge[i][j]:
indeg[j] -= 1
if indeg[j] == 0:
queue.append(j)
return "".join(order) if len(order) == len(present) else "" # letters left over: a cycle
for words in (["dcb", "dca", "cb", "ba"], ["dc", "cd", "dc"]):
print(" ".join(words), '-> "' + alien_order(words) + '"')
# dcb dca cb ba -> "dcba"
# dc cd dc -> ""import java.util.*;
public class Main {
static String alienOrder(String[] words) { // Alien Dictionary: the letters' order, from words already sorted
boolean[] present = new boolean[26];
int count = 0;
for (String w : words) for (char ch : w.toCharArray()) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int k = 0; k + 1 < words.length; k++) { // each pair of neighbouring words gives one rule at most
String a = words[k], b = words[k + 1];
int i = 0;
while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
if (i < a.length() && i < b.length()) { // the first letters that differ: a's comes before b's
int x = a.charAt(i) - 'a', y = b.charAt(i) - 'a';
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (a.length() > b.length()) {
return ""; // a word before its own prefix: no order allows that
}
}
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) queue.add(c);
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
int c = queue.poll();
order.append((char) ('a' + c));
for (int d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] == 0) queue.add(d);
}
return order.length() == count ? order.toString() : ""; // letters left over: a cycle
}
public static void main(String[] args) {
String[][] cases = {{"dcb", "dca", "cb", "ba"}, {"dc", "cd", "dc"}};
for (String[] words : cases) System.out.println(String.join(" ", words) + " -> \"" + alienOrder(words) + "\"");
}
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""#include <bits/stdc++.h>
using namespace std;
string alienOrder(const vector<string>& words) { // Alien Dictionary: the letters' order, from sorted words
bool present[26] = {}, edge[26][26] = {};
int indeg[26] = {}, count = 0;
for (auto& w : words) for (char ch : w) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
for (size_t k = 0; k + 1 < words.size(); k++) { // each pair of neighbouring words gives one rule at most
const string &a = words[k], &b = words[k + 1];
size_t i = 0;
while (i < a.size() && i < b.size() && a[i] == b[i]) i++;
if (i < a.size() && i < b.size()) { // the first letters that differ: a's comes before b's
int x = a[i] - 'a', y = b[i] - 'a';
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (a.size() > b.size()) {
return ""; // a word before its own prefix: no order allows that
}
}
queue<int> q;
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) q.push(c);
string order;
while (!q.empty()) {
int c = q.front();
q.pop();
order += char('a' + c);
for (int d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] == 0) q.push(d);
}
return (int) order.size() == count ? order : ""; // letters left over: a cycle
}
int main() {
vector<vector<string>> cases = {{"dcb", "dca", "cb", "ba"}, {"dc", "cd", "dc"}};
for (auto& words : cases) {
for (size_t i = 0; i < words.size(); i++) cout << (i ? " " : "") << words[i];
cout << " -> \"" << alienOrder(words) << "\"\n";
}
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""function alienOrder(words) { // Alien Dictionary: the letters' order, from words already sorted
const code = (ch) => ch.charCodeAt(0) - 97;
const present = new Array(26).fill(false);
for (const w of words) for (const ch of w) present[code(ch)] = true;
const count = present.filter(Boolean).length;
const edge = Array.from({ length: 26 }, () => new Array(26).fill(false));
const indeg = new Array(26).fill(0);
for (let k = 0; k + 1 < words.length; k++) { // each pair of neighbouring words gives one rule at most
const a = words[k], b = words[k + 1];
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) i++;
if (i < a.length && i < b.length) { // the first letters that differ: a's comes before b's
const x = code(a[i]), y = code(b[i]);
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (a.length > b.length) {
return ""; // a word before its own prefix: no order allows that
}
}
const queue = [];
for (let c = 0; c < 26; c++) if (present[c] && indeg[c] === 0) queue.push(c);
let order = "";
for (let head = 0; head < queue.length; head++) {
const c = queue[head];
order += String.fromCharCode(97 + c);
for (let d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] === 0) queue.push(d);
}
return order.length === count ? order : ""; // letters left over: a cycle
}
for (const words of [["dcb", "dca", "cb", "ba"], ["dc", "cd", "dc"]]) {
console.log(`${words.join(" ")} -> "${alienOrder(words)}"`);
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""function alienOrder(words: string[]): string { // Alien Dictionary: the letters' order, from words already sorted
const code = (ch: string): number => ch.charCodeAt(0) - 97;
const present = new Array<boolean>(26).fill(false);
for (const w of words) for (const ch of w) present[code(ch)] = true;
const count = present.filter(Boolean).length;
const edge: boolean[][] = Array.from({ length: 26 }, () => new Array<boolean>(26).fill(false));
const indeg = new Array<number>(26).fill(0);
for (let k = 0; k + 1 < words.length; k++) { // each pair of neighbouring words gives one rule at most
const a = words[k], b = words[k + 1];
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) i++;
if (i < a.length && i < b.length) { // the first letters that differ: a's comes before b's
const x = code(a[i]), y = code(b[i]);
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (a.length > b.length) {
return ""; // a word before its own prefix: no order allows that
}
}
const queue: number[] = [];
for (let c = 0; c < 26; c++) if (present[c] && indeg[c] === 0) queue.push(c);
let order = "";
for (let head = 0; head < queue.length; head++) {
const c = queue[head];
order += String.fromCharCode(97 + c);
for (let d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] === 0) queue.push(d);
}
return order.length === count ? order : ""; // letters left over: a cycle
}
for (const words of [["dcb", "dca", "cb", "ba"], ["dc", "cd", "dc"]]) {
console.log(`${words.join(" ")} -> "${alienOrder(words)}"`);
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""using System;
using System.Collections.Generic;
using System.Text;
class Program {
static string AlienOrder(string[] words) { // Alien Dictionary: the letters' order, from words already sorted
var present = new bool[26];
int count = 0;
foreach (var w in words) foreach (char ch in w) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
var edge = new bool[26, 26];
var indeg = new int[26];
for (int k = 0; k + 1 < words.Length; k++) { // each pair of neighbouring words gives one rule at most
string a = words[k], b = words[k + 1];
int i = 0;
while (i < a.Length && i < b.Length && a[i] == b[i]) i++;
if (i < a.Length && i < b.Length) { // the first letters that differ: a's comes before b's
int x = a[i] - 'a', y = b[i] - 'a';
if (!edge[x, y]) {
edge[x, y] = true;
indeg[y]++;
}
} else if (a.Length > b.Length) {
return ""; // a word before its own prefix: no order allows that
}
}
var queue = new Queue<int>();
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) queue.Enqueue(c);
var order = new StringBuilder();
while (queue.Count > 0) {
int c = queue.Dequeue();
order.Append((char) ('a' + c));
for (int d = 0; d < 26; d++) if (edge[c, d] && --indeg[d] == 0) queue.Enqueue(d);
}
return order.Length == count ? order.ToString() : ""; // letters left over: a cycle
}
static void Main() {
var cases = new[] { new[] { "dcb", "dca", "cb", "ba" }, new[] { "dc", "cd", "dc" } };
foreach (var words in cases) Console.WriteLine($"{string.Join(" ", words)} -> \"{AlienOrder(words)}\"");
}
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""package main
import (
"fmt"
"strings"
)
func alienOrder(words []string) string { // Alien Dictionary: the letters' order, from words already sorted
var present [26]bool
var edge [26][26]bool
var indeg [26]int
count := 0
for _, w := range words {
for _, ch := range w {
if !present[ch-'a'] {
present[ch-'a'] = true
count++
}
}
}
for k := 0; k+1 < len(words); k++ { // each pair of neighbouring words gives one rule at most
a, b := words[k], words[k+1]
i := 0
for i < len(a) && i < len(b) && a[i] == b[i] {
i++
}
if i < len(a) && i < len(b) { // the first letters that differ: a's comes before b's
x, y := a[i]-'a', b[i]-'a'
if !edge[x][y] {
edge[x][y] = true
indeg[y]++
}
} else if len(a) > len(b) {
return "" // a word before its own prefix: no order allows that
}
}
queue := []int{}
for c := 0; c < 26; c++ {
if present[c] && indeg[c] == 0 {
queue = append(queue, c)
}
}
order := []byte{}
for head := 0; head < len(queue); head++ {
c := queue[head]
order = append(order, byte('a'+c))
for d := 0; d < 26; d++ {
if edge[c][d] {
indeg[d]--
if indeg[d] == 0 {
queue = append(queue, d)
}
}
}
}
if len(order) != count { // letters left over: a cycle
return ""
}
return string(order)
}
func main() {
for _, words := range [][]string{{"dcb", "dca", "cb", "ba"}, {"dc", "cd", "dc"}} {
fmt.Printf("%s -> \"%s\"\n", strings.Join(words, " "), alienOrder(words))
}
}
// dcb dca cb ba -> "dcba"
// dc cd dc -> ""dcb before dca says b comes before a; dca before cb, d before c; cb before ba, c before b: one order, d c b a. dc, cd, dc says d before c and c before d, a cycle, so the answer is empty.
Which one to use
| The question | Use | Watch for |
|---|---|---|
| A cycle in an undirected graph? A tree? | A search with parents; n − 1 edges | Two edges, one pair |
| A cycle in a directed graph? | DFS with three states | Seen isn't a cycle |
| Two groups, every edge between them? | Two colours by BFS | Every part needs a start |
| An order with every edge forward? | Reversed finishing order, or Kahn's | A cycle: no order |
| What's stuck, or unsafe? | Kahn's leftovers, or three states | What's after a cycle too |
| The middle of a tree? | Peel the leaves | One or two centres |
Near misses: finding cycles while edges arrive one by one is Union-Find and Minimum Spanning Trees; the shortest path through a DAG with weights uses this order in Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall; and splitting a directed graph into groups that all reach each other is Bridges, Articulation Points and Strong Components.
Mistakes that look right
Two of these run below in every language. The others are just as common:
- A mark for seen in a directed graph: a diamond looks like a cycle, as the 55 courses above showed.
- A mark for the path only: right, but it walks every path, 4,194,163 calls where 55 do.
- Two colours from vertex 0 only: a part of the graph that 0 can't reach is never checked.
- Kahn's without counting: a cycle leaves vertices out and the order looks done; compare the count with n.
- The prefix pair in Alien Dictionary: dcab before dca has no answer, but the letters' edges alone don't say so.
- The parent check by vertex, with two edges between one pair: the second edge back is a cycle.
- The edges turned around: [course, needs] means needs → course; the other way gives the order backwards.
from collections import deque
def bipartite(graph, every_start): # two colours, from vertex 0 only or from every uncoloured vertex
colour = [-1] * len(graph)
for s in (range(len(graph)) if every_start else [0]):
if colour[s] != -1:
continue
colour[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for v in graph[u]:
if colour[v] == -1:
colour[v] = 1 - colour[u]
queue.append(v)
elif colour[v] == colour[u]:
return False
return True
def alien_order(words, check_prefix): # Alien Dictionary, with or without the prefix check
present = sorted(set("".join(words)))
edge, indeg = [[False] * 26 for _ in range(26)], [0] * 26
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
i, j = ord(x) - 97, ord(y) - 97
if not edge[i][j]:
edge[i][j] = True
indeg[j] += 1
break
else:
if check_prefix and len(a) > len(b):
return ""
queue = deque(ord(c) - 97 for c in present if indeg[ord(c) - 97] == 0)
order = []
while queue:
i = queue.popleft()
order.append(chr(97 + i))
for j in range(26):
if edge[i][j]:
indeg[j] -= 1
if indeg[j] == 0:
queue.append(j)
return "".join(order) if len(order) == len(present) else ""
graph = [[1, 3], [0, 2], [1, 3], [0, 2], [5, 6], [4, 6], [4, 5]] # a square, and a triangle apart from it
word = lambda ok: "bipartite" if ok else "not bipartite"
print("from vertex 0 only:", word(bipartite(graph, False)), "| from every vertex:", word(bipartite(graph, True)))
print('dcab before dca, no prefix check: "' + alien_order(["dcab", "dca"], False) + '" | with it: "'
+ alien_order(["dcab", "dca"], True) + '"')
# from vertex 0 only: bipartite | from every vertex: not bipartite
# dcab before dca, no prefix check: "abcd" | with it: ""import java.util.*;
public class Main {
static boolean bipartite(int[][] graph, boolean everyStart) { // from vertex 0 only, or every uncoloured one
int n = graph.length;
int[] colour = new int[n];
Arrays.fill(colour, -1);
for (int s = 0; s < (everyStart ? n : 1); s++) {
if (colour[s] != -1) continue;
colour[s] = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u];
queue.add(v);
} else if (colour[v] == colour[u]) {
return false;
}
}
}
}
return true;
}
static String alienOrder(String[] words, boolean checkPrefix) { // with or without the prefix check
boolean[] present = new boolean[26];
int count = 0;
for (String w : words) for (char ch : w.toCharArray()) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
boolean[][] edge = new boolean[26][26];
int[] indeg = new int[26];
for (int k = 0; k + 1 < words.length; k++) {
String a = words[k], b = words[k + 1];
int i = 0;
while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
if (i < a.length() && i < b.length()) {
int x = a.charAt(i) - 'a', y = b.charAt(i) - 'a';
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (checkPrefix && a.length() > b.length()) {
return "";
}
}
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) queue.add(c);
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
int c = queue.poll();
order.append((char) ('a' + c));
for (int d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] == 0) queue.add(d);
}
return order.length() == count ? order.toString() : "";
}
static String word(boolean ok) {
return ok ? "bipartite" : "not bipartite";
}
public static void main(String[] args) {
int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5, 6}, {4, 6}, {4, 5}}; // a square, and a triangle apart
System.out.println("from vertex 0 only: " + word(bipartite(graph, false)) + " | from every vertex: "
+ word(bipartite(graph, true)));
String[] words = {"dcab", "dca"};
System.out.println("dcab before dca, no prefix check: \"" + alienOrder(words, false) + "\" | with it: \""
+ alienOrder(words, true) + "\"");
}
}
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""#include <bits/stdc++.h>
using namespace std;
bool bipartite(const vector<vector<int>>& graph, bool everyStart) { // from vertex 0 only, or every uncoloured
int n = graph.size();
vector<int> colour(n, -1);
for (int s = 0; s < (everyStart ? n : 1); s++) {
if (colour[s] != -1) continue;
colour[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u];
q.push(v);
} else if (colour[v] == colour[u]) {
return false;
}
}
}
}
return true;
}
string alienOrder(const vector<string>& words, bool checkPrefix) { // with or without the prefix check
bool present[26] = {}, edge[26][26] = {};
int indeg[26] = {}, count = 0;
for (auto& w : words) for (char ch : w) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
for (size_t k = 0; k + 1 < words.size(); k++) {
const string &a = words[k], &b = words[k + 1];
size_t i = 0;
while (i < a.size() && i < b.size() && a[i] == b[i]) i++;
if (i < a.size() && i < b.size()) {
int x = a[i] - 'a', y = b[i] - 'a';
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (checkPrefix && a.size() > b.size()) {
return "";
}
}
queue<int> q;
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) q.push(c);
string order;
while (!q.empty()) {
int c = q.front();
q.pop();
order += char('a' + c);
for (int d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] == 0) q.push(d);
}
return (int) order.size() == count ? order : "";
}
string word(bool ok) { return ok ? "bipartite" : "not bipartite"; }
int main() {
vector<vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5, 6}, {4, 6}, {4, 5}}; // a square, a triangle
cout << "from vertex 0 only: " << word(bipartite(graph, false)) << " | from every vertex: "
<< word(bipartite(graph, true)) << "\n";
cout << "dcab before dca, no prefix check: \"" << alienOrder({"dcab", "dca"}, false) << "\" | with it: \""
<< alienOrder({"dcab", "dca"}, true) << "\"\n";
}
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""function bipartite(graph, everyStart) { // two colours, from vertex 0 only or from every uncoloured vertex
const colour = new Array(graph.length).fill(-1);
for (let s = 0; s < (everyStart ? graph.length : 1); s++) {
if (colour[s] !== -1) continue;
colour[s] = 0;
const queue = [s];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (colour[v] === -1) {
colour[v] = 1 - colour[u];
queue.push(v);
} else if (colour[v] === colour[u]) {
return false;
}
}
}
}
return true;
}
function alienOrder(words, checkPrefix) { // Alien Dictionary, with or without the prefix check
const code = (ch) => ch.charCodeAt(0) - 97;
const present = new Array(26).fill(false);
for (const w of words) for (const ch of w) present[code(ch)] = true;
const count = present.filter(Boolean).length;
const edge = Array.from({ length: 26 }, () => new Array(26).fill(false));
const indeg = new Array(26).fill(0);
for (let k = 0; k + 1 < words.length; k++) {
const a = words[k], b = words[k + 1];
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) i++;
if (i < a.length && i < b.length) {
const x = code(a[i]), y = code(b[i]);
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (checkPrefix && a.length > b.length) {
return "";
}
}
const queue = [];
for (let c = 0; c < 26; c++) if (present[c] && indeg[c] === 0) queue.push(c);
let order = "";
for (let head = 0; head < queue.length; head++) {
const c = queue[head];
order += String.fromCharCode(97 + c);
for (let d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] === 0) queue.push(d);
}
return order.length === count ? order : "";
}
const graph = [[1, 3], [0, 2], [1, 3], [0, 2], [5, 6], [4, 6], [4, 5]]; // a square, and a triangle apart from it
const word = (ok) => (ok ? "bipartite" : "not bipartite");
console.log(`from vertex 0 only: ${word(bipartite(graph, false))} | from every vertex: ${word(bipartite(graph, true))}`);
console.log(`dcab before dca, no prefix check: "${alienOrder(["dcab", "dca"], false)}" | with it: "${
alienOrder(["dcab", "dca"], true)}"`);
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""function bipartite(graph: number[][], everyStart: boolean): boolean { // from vertex 0 only, or every one
const colour = new Array<number>(graph.length).fill(-1);
for (let s = 0; s < (everyStart ? graph.length : 1); s++) {
if (colour[s] !== -1) continue;
colour[s] = 0;
const queue = [s];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of graph[u]) {
if (colour[v] === -1) {
colour[v] = 1 - colour[u];
queue.push(v);
} else if (colour[v] === colour[u]) {
return false;
}
}
}
}
return true;
}
function alienOrder(words: string[], checkPrefix: boolean): string { // with or without the prefix check
const code = (ch: string): number => ch.charCodeAt(0) - 97;
const present = new Array<boolean>(26).fill(false);
for (const w of words) for (const ch of w) present[code(ch)] = true;
const count = present.filter(Boolean).length;
const edge: boolean[][] = Array.from({ length: 26 }, () => new Array<boolean>(26).fill(false));
const indeg = new Array<number>(26).fill(0);
for (let k = 0; k + 1 < words.length; k++) {
const a = words[k], b = words[k + 1];
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) i++;
if (i < a.length && i < b.length) {
const x = code(a[i]), y = code(b[i]);
if (!edge[x][y]) {
edge[x][y] = true;
indeg[y]++;
}
} else if (checkPrefix && a.length > b.length) {
return "";
}
}
const queue: number[] = [];
for (let c = 0; c < 26; c++) if (present[c] && indeg[c] === 0) queue.push(c);
let order = "";
for (let head = 0; head < queue.length; head++) {
const c = queue[head];
order += String.fromCharCode(97 + c);
for (let d = 0; d < 26; d++) if (edge[c][d] && --indeg[d] === 0) queue.push(d);
}
return order.length === count ? order : "";
}
const graph: number[][] = [[1, 3], [0, 2], [1, 3], [0, 2], [5, 6], [4, 6], [4, 5]]; // a square, a triangle apart
const word = (ok: boolean): string => (ok ? "bipartite" : "not bipartite");
console.log(`from vertex 0 only: ${word(bipartite(graph, false))} | from every vertex: ${word(bipartite(graph, true))}`);
console.log(`dcab before dca, no prefix check: "${alienOrder(["dcab", "dca"], false)}" | with it: "${
alienOrder(["dcab", "dca"], true)}"`);
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""using System;
using System.Collections.Generic;
using System.Text;
class Program {
static bool Bipartite(int[][] graph, bool everyStart) { // two colours, from vertex 0 only or every uncoloured one
int n = graph.Length;
var colour = new int[n];
Array.Fill(colour, -1);
for (int s = 0; s < (everyStart ? n : 1); s++) {
if (colour[s] != -1) continue;
colour[s] = 0;
var queue = new Queue<int>();
queue.Enqueue(s);
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (colour[v] == -1) {
colour[v] = 1 - colour[u];
queue.Enqueue(v);
} else if (colour[v] == colour[u]) {
return false;
}
}
}
}
return true;
}
static string AlienOrder(string[] words, bool checkPrefix) { // Alien Dictionary, with or without the prefix check
var present = new bool[26];
int count = 0;
foreach (var w in words) foreach (char ch in w) if (!present[ch - 'a']) { present[ch - 'a'] = true; count++; }
var edge = new bool[26, 26];
var indeg = new int[26];
for (int k = 0; k + 1 < words.Length; k++) {
string a = words[k], b = words[k + 1];
int i = 0;
while (i < a.Length && i < b.Length && a[i] == b[i]) i++;
if (i < a.Length && i < b.Length) {
int x = a[i] - 'a', y = b[i] - 'a';
if (!edge[x, y]) {
edge[x, y] = true;
indeg[y]++;
}
} else if (checkPrefix && a.Length > b.Length) {
return "";
}
}
var queue = new Queue<int>();
for (int c = 0; c < 26; c++) if (present[c] && indeg[c] == 0) queue.Enqueue(c);
var order = new StringBuilder();
while (queue.Count > 0) {
int c = queue.Dequeue();
order.Append((char) ('a' + c));
for (int d = 0; d < 26; d++) if (edge[c, d] && --indeg[d] == 0) queue.Enqueue(d);
}
return order.Length == count ? order.ToString() : "";
}
static string Word(bool ok) => ok ? "bipartite" : "not bipartite";
static void Main() {
int[][] graph = { new[] {1, 3}, new[] {0, 2}, new[] {1, 3}, new[] {0, 2}, new[] {5, 6}, new[] {4, 6}, new[] {4, 5} };
Console.WriteLine($"from vertex 0 only: {Word(Bipartite(graph, false))} | from every vertex: {Word(Bipartite(graph, true))}");
var words = new[] { "dcab", "dca" };
Console.WriteLine($"dcab before dca, no prefix check: \"{AlienOrder(words, false)}\" | with it: \"{AlienOrder(words, true)}\"");
}
}
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""package main
import "fmt"
func bipartite(graph [][]int, everyStart bool) bool { // two colours, from vertex 0 only or every uncoloured one
n := len(graph)
colour := make([]int, n)
for i := range colour {
colour[i] = -1
}
starts := 1
if everyStart {
starts = n
}
for s := 0; s < starts; s++ {
if colour[s] != -1 {
continue
}
colour[s] = 0
queue := []int{s}
for head := 0; head < len(queue); head++ {
u := queue[head]
for _, v := range graph[u] {
if colour[v] == -1 {
colour[v] = 1 - colour[u]
queue = append(queue, v)
} else if colour[v] == colour[u] {
return false
}
}
}
}
return true
}
func alienOrder(words []string, checkPrefix bool) string { // Alien Dictionary, with or without the prefix check
var present [26]bool
var edge [26][26]bool
var indeg [26]int
count := 0
for _, w := range words {
for _, ch := range w {
if !present[ch-'a'] {
present[ch-'a'] = true
count++
}
}
}
for k := 0; k+1 < len(words); k++ {
a, b := words[k], words[k+1]
i := 0
for i < len(a) && i < len(b) && a[i] == b[i] {
i++
}
if i < len(a) && i < len(b) {
x, y := a[i]-'a', b[i]-'a'
if !edge[x][y] {
edge[x][y] = true
indeg[y]++
}
} else if checkPrefix && len(a) > len(b) {
return ""
}
}
queue := []int{}
for c := 0; c < 26; c++ {
if present[c] && indeg[c] == 0 {
queue = append(queue, c)
}
}
order := []byte{}
for head := 0; head < len(queue); head++ {
c := queue[head]
order = append(order, byte('a'+c))
for d := 0; d < 26; d++ {
if edge[c][d] {
indeg[d]--
if indeg[d] == 0 {
queue = append(queue, d)
}
}
}
}
if len(order) != count {
return ""
}
return string(order)
}
func word(ok bool) string {
if ok {
return "bipartite"
}
return "not bipartite"
}
func main() {
graph := [][]int{{1, 3}, {0, 2}, {1, 3}, {0, 2}, {5, 6}, {4, 6}, {4, 5}} // a square, and a triangle apart from it
fmt.Printf("from vertex 0 only: %s | from every vertex: %s\n", word(bipartite(graph, false)), word(bipartite(graph, true)))
words := []string{"dcab", "dca"}
fmt.Printf("dcab before dca, no prefix check: \"%s\" | with it: \"%s\"\n", alienOrder(words, false), alienOrder(words, true))
}
// from vertex 0 only: bipartite | from every vertex: not bipartite
// dcab before dca, no prefix check: "abcd" | with it: ""From vertex 0 the square checks out and the triangle 4, 5, 6 is never looked at: bipartite, wrongly. Without the prefix check, dcab before dca gives no edge at all, and the four letters come out as abcd where the empty answer is right.
Check yourself
Quiz
1 / 6Multiple choice
A DFS on a directed graph reaches a vertex it has already finished. What does that say?
Multiple choice
A graph has 5 vertices and the edges [0, 1], [1, 2], [2, 0] and [3, 4]. Is it a tree?
Multiple choice
Is a ring of 7 vertices bipartite? And a ring of 8?
Multiple choice
Kahn's algorithm runs on 5 vertices with the edges [2, 0], [2, 1], [0, 3], [1, 3] and [3, 4], taking each vertex's edges in that order. Which order comes out?
Multiple choice
In a graph with no cycle, why does reversed DFS finishing order put every edge forward?
Multiple choice
Which roots give the shortest trees for the path 0-1-2-3-4-5?
Practice
The problems in this group, each mapped to the idea it trains:
- Detect Cycle in Undirected Graph: a marked neighbour that isn't the parent.
- Graph Valid Tree: n − 1 edges and no cycle.
- Is Graph Bipartite?: two colours, a start for every part.
- Detect Cycle in Directed Graph: three states, an edge back to the path.
- Course Schedule: every course finishable means no cycle.
- Topological Sort: reversed finishing order.
- Kahn's Algorithm (BFS Topo Sort): in-degrees and a queue.
- Course Schedule II: the order, or nothing when a cycle is left.
- Course Schedule IV: what comes before what, a row per course in order.
- Find Eventual Safe States: no path into a cycle.
- Minimum Height Trees: peel the leaves to the centre.
- Alien Dictionary: one edge per pair of words, and the prefix check.