Euler's Formula

Introduction

A planar graph is a graph that can be drawn on a plane without any edges crossing. In other words, it can be embedded in the plane such that no two edges intersect except at their endpoints.

Euler's Formula

Euler's Formula states that any correct embedding of a connected planar graph satistfies:-

$V = Vertices$

$E = Edges$

$F = Faces$

Example 1

Explanation

Intuition

In this problem, we're asked to count the number of contiguous areas of cells on several flat rectangles. Such areas are separated by river segments and rectangle boundaries.

Where else do we count the number of areas on a flat surface?

That's right - we use Euler's formula to count the number of faces of a planar graph. This suggests that we should turn our rectangles into planar graphs.

Making the Planar Graph

We can turn a rectangle into a planar graph as so:

• Put temporary river segments outside the border of the rectangle.
• For each river segment, we insert its 4 corners into a set of nodes and its 4 sides into a set of edges.

Notice how the resulting graph is planar, so we can apply Euler's formula.

Applying Euler's Formula

For a planar graph, Euler's formula is given as $F = E - V + 1 + C$, where $F$ is the number of faces (including the background face), $E$ is the number of edges, $V$ is the number of vertices, and $C$ is the number of connected components.

Notice how $F$ in our planar graph is equal to $1 + R + A$, where $R$ is the number of river segments and $A$ is the answer to the query. This means we must subtract $R + 1$ from $F$ to get $A$.

Since the whole river is a big connected component, we can just check whether the river touches the bounding rectangle to determine $C$.

Finding $E$, $V$, and $R$ is a lot more complicated though.

Finding $E$, $V$, and $R$

To find $E$, $V$, and $R$, we can use a data structure that can handle 2D range queries efficiently.

However, the coordinates of the grid can get very large, so a simple 2D BIT or segment tree won't work here.

To work around this, we can either use a 2D BIT with coordinate compression or a persistent segment tree. See the sections on offline 2D sum queries or persistent segment trees for more details.

Implementation

With a persistent segment tree.

Time Complexity: $\mathcal{O}(N \log N)$

Memory Complexity: $\mathcal{O}(N \log N)$

Copy
const int MAXN = 2e5, MAXSEGMENT = (6e5 + 9) * 19 + 1;

int cnt = 1, segtree[MAXSEGMENT], left_c[MAXSEGMENT], right_c[MAXSEGMENT];

struct Segtree {
	set<int> data[MAXN + 1];
	int roots[MAXN + 2];

	void add(int x, int y) { data[x].insert(y); }

Example 2

Explanation

This problem involves a 2D grid. The code tracks connected region of points using heights. We will use Disjoint Set Union (DSU). As we process points by increasing height, we merge them into regions and update the answer based on their size. The logic here mirrors an application of Euler's formula for planar graphs, where we maintain boundaries (faces) as we mege points (vertices) and check their connectivity (edges).

Implementation

With Euler's Formula

Time Complexity: $\mathcal{O}(N^2 \log N)$

Memory Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

Problems