Recently I came across this problem from IARCS Problem Archive , and after some research , the answer seems to be tarjan's algorithm to find the points which when deleted , breaks the graph in two or more smaller graphs .
What is the best way to represent adjacency lists in C++98by Tanavya Dimri
INOI is coming up soon, and seeing that only C++98 was provided in ZCO, I won't be surprised (but would be upset) that they provide the same in INOI.
Normally I represent undirected graphs as an unordered_map of vectors, like this:
unordered_map <int, vector <int>> graph;
For directed graphs, I may use an unordered_map of unordered_maps to store the weights.
However, what is the best way to do so in C++98, especially for sparse graphs. Do I have to resort to something like: int graph[n][n] which would consume quite a lot of space, as it is basically just an adjacency matrix.