Disjoint Set Union (DSU) Part 2

Disjoint Set Union (DSU) Part 2

Introduction

DSU is usually introduced as a data structure for connected components. It answers questions like: are two vertices already in the same component, and what happens if we add an edge between them?

But DSU can do more than just connectivity. Sometimes, each component has extra information attached to it. In this lecture, we will solve a more interesting problem: edges are added one by one, and after every added edge we must know whether the graph is still bipartite.

A graph is bipartite if we can color every vertex with two colors, for example color 0 and color 1, so that every edge connects vertices of different colors. The important idea is that DSU can store not only the leader of each component, but also the relation between a vertex and its leader.

By the end of this lecture, students should understand how to store extra information on the DSU tree and how to use it while merging components.

Problem or motivation

We have $n$ vertices and no edges at the beginning. Then $q$ edges are added one by one.

After each added edge $(u, v)$, print:

• YES if the whole graph is still bipartite.
• NO if the graph is no longer bipartite.

Once the graph becomes not bipartite, it will stay not bipartite, because we only add edges and never remove them.

For example, if we add edges , , and then , the third edge creates a triangle. A triangle has odd length, so it cannot be bipartite.