This blog explains the standard technique used in problems like 920E - Связные компоненты?

What is Complement Graph?

Suppose we have a graph Vertices : 1 2 3 4 Edges : 1-2, 2-3

Original Graph :

Complement Graph:

Why Can't We Build Complement Graph?

Suppose : n <= 200000 m <= 200000

The complement graph may contain ≈ n² / 2 edges which is ≈ 2 × 10¹⁰ Impossible to store.

So we need another idea.

Key Observation

Suppose we are currently standing at vertex u

Who are the neighbours of u in the complement graph?

Exactly those vertices

• which are still unvisited and which are NOT adjacent to u in the original graph

In other words

Complement Neighbours = All Unvisited Vertices - Original Neighbours

Idea

The complement graph is usually too large to construct explicitly.

Instead of storing the complement graph, store the original graph.

During BFS/DFS, for every current node u, every unvisited vertex that is not adjacent to u in the original graph is a neighbour in the complement graph.

Data Structures

1. blocked

vector<set<int>> blocked(n + 1);

blocked[u] stores all neighbours of u in the original graph.

Checking

blocked[u].find(v) == blocked[u].end()

means that (u, v) does not exist in the original graph, so it does exist in the complement graph.

2. unvisited

set<int> unvisited;

Initially,

{1,2,3,...,n}

Whenever a node is visited, remove it from this set.

Thus, unvisited always contains the vertices that haven't been explored yet.

Algorithm

1. Store the original graph in blocked.
2. Put every vertex into unvisited.
3. While unvisited is not empty:

• Pick any vertex and start BFS/DFS.
• For every node u popped from the queue, iterate through all vertices in unvisited.
• If v is not in blocked[u], then (u, v) is a complement edge.
• Visit v and remove it from unvisited.

1. The number of visited vertices gives the size of one connected component.

Code Walkthrough

Build the original graph

vector<set<int>> blocked(n + 1);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    blocked[u].insert(v);
    blocked[v].insert(u);
}

Initially every node is unvisited

set<int> unvisited;

for (int i = 1; i <= n; i++)
    unvisited.insert(i);

Start BFS from any remaining vertex

int startNode = *unvisited.begin();
unvisited.erase(startNode);

queue<int> q;
q.push(startNode);

Find complement neighbours

for (auto &v : unvisited) {
    if (blocked[u].find(v) == blocked[u].end()) {
        toremove.push_back(v);
        q.push(v);
    }
}

If v is not an original neighbour of u, then it is a neighbour in the complement graph.

Remove newly visited vertices

for (auto &x : toremove)
    unvisited.erase(x);

We remove them after the loop because modifying a set while iterating over it is unsafe.

Time Complexity

• Building the graph: O(m log n)
• Each edge lookup: O(log n)

The overall time complexity is: O((n + m) log n). Solution Link — 382152731

Practice Problem:

• 190E - Контрнаступление

• 1242B - 0-1 MST