This blog explains the standard technique used in problems like [problem: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`↵
↵
```cpp↵
vector<set<int>> blocked(n + 1);↵
```↵
↵
`blocked[u]` stores all neighbours of `u` in the **original graph**.↵
↵
Checking↵
↵
```cpp↵
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`↵
↵
```cpp↵
set<int> unvisited;↵
```↵
↵
Initially,↵
↵
```text↵
{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`.↵
4. The number of visited vertices gives the size of one connected component.↵
↵
---↵
↵
### Code Walkthrough↵
↵
#### Build the original graph↵
↵
```cpp↵
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↵
↵
```cpp↵
set<int> unvisited;↵
↵
for (int i = 1; i <= n; i++)↵
unvisited.insert(i);↵
```↵
↵
---↵
↵
#### Start BFS from any remaining vertex↵
↵
```cpp↵
int startNode = *unvisited.begin();↵
unvisited.erase(startNode);↵
↵
queue<int> q;↵
q.push(startNode);↵
```↵
↵
---↵
↵
### Find complement neighbours↵
↵
```cpp↵
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↵
↵
```cpp↵
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 above implementation is simple but can take **O(n² log n)** in the worst case.↵
↵
The optimized solution for CF 920E uses a smarter way of traversing `unvisited`, achieving **O((n + m) log n)**.↵
Solution Link — [submission:382152731]↵
↵
Practice Problem:↵
↵
- [problem:190E]↵
↵
- [problem:1242B]
↵
#### 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`↵
↵
```cpp↵
vector<set<int>> blocked(n + 1);↵
```↵
↵
`blocked[u]` stores all neighbours of `u` in the **original graph**.↵
↵
Checking↵
↵
```cpp↵
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`↵
↵
```cpp↵
set<int> unvisited;↵
```↵
↵
Initially,↵
↵
```text↵
{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`.↵
4. The number of visited vertices gives the size of one connected component.↵
↵
---↵
↵
### Code Walkthrough↵
↵
#### Build the original graph↵
↵
```cpp↵
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↵
↵
```cpp↵
set<int> unvisited;↵
↵
for (int i = 1; i <= n; i++)↵
unvisited.insert(i);↵
```↵
↵
---↵
↵
#### Start BFS from any remaining vertex↵
↵
```cpp↵
int startNode = *unvisited.begin();↵
unvisited.erase(startNode);↵
↵
queue<int> q;↵
q.push(startNode);↵
```↵
↵
---↵
↵
### Find complement neighbours↵
↵
```cpp↵
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↵
↵
```cpp↵
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 above implementation is simple but can take **O(n² log n)** in the worst case.↵
↵
The optimized solution for CF 920E uses a smarter way of traversing `unvisited`, achieving **O((n + m) log n)**.↵
Solution Link — [submission:382152731]↵
↵
Practice Problem:↵
↵
- [problem:190E]↵
↵
- [problem:1242B]
