This page needs to be organised and partitioned down to multiple pages

  • A graph is bipartite if it is possible to color it using two colors. It turns out that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges.

Krushkal’s algorithm

  • Minimum Spanning Tree
  • Use dsu and priority queue

Rerooting the Tree

void change_root(int old_root, int new_root) {
    // Update data structures as if `new_root` was being removed as a child from `old_root`
    // Update data structures as if `old_root` was being added as a child to `new_root`
}

void walk(int vertex, int parent) {
    // Data structures now reflect the tree as if `vertex` were the root

    for (child in adjacency_list[vertex]) {
        if (child == parent) continue;

        change_root(vertex, child);
        walk(child, vertex);
        change_root(child, vertex);
    }
}

// Initialize data structures with respect to the initial root `root`

walk(root, -1);

Resources

Problems