Condensation of the graph#1947

Condensation of the graph (Editorial)

First find the strongly connected components of the graph. All vertices belonging to the same strongly connected component are assigned the same unique color. Let $co l or [i]$ color[i] denote the color of the $i$ -th vertex. The number of used colors is equal to the number of strongly connected components.

Iterate over all edges of the original graph. If an edge connects vertices with different colors, then it corresponds to an edge in the condensation graph. For each edge $(a, b)$ such that $co l or [a] \neq = co l or [b]$ color[a] \ne color[b], add the pair $(co l or [a], co l or [b])$ (color[a], color[b]) to the set $s$ . Since a set is used rather than a multiset, duplicate pairs are not counted.

The number of elements in the set $s$ is equal to the number of edges in the condensation graph.

Example

The graph shown in the example has the following structure:

The condensation of the graph consists of three vertices and two edges.

Algorithm implementation

The input graph is stored as an adjacency list $g$ . The reversed graph (a graph in which the directions of all edges are inverted) is stored as an adjacency list $g r$ . The edges of the condensed graph are stored in a set of pairs $s$ .

vector<vector<int> > g, gr;
vector<int> used, top, color;
set<pair<int,int> > s;

The function dfs1 performs a depth-first search on the input graph. The array $t o p$ stores the vertices in the order in which their processing is completed by the depth-first search algorithm.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

C++

The function dfs2 performs a depth-first search on the reversed graph. All vertices visited during the recursive calls of dfs2 belong to the same strongly connected component. All such vertices are colored with color $c$ .

void dfs2(int v, int c)
{
  color[v] = c;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, c);
}

The main part of the program. Read the input data and construct the reversed graph.

scanf("%d %d", &n, &m);
g.resize(n+1);
gr.resize(n+1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b); 
  gr[b].push_back(a);
}

C++

Start a depth-first search on the input graph. The order in which vertex processing is completed is stored in the array $t o p$ .

used.resize(n+1);
for(i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

Run a depth-first search on the reversed graph. The vertices of the reversed graph are processed in the order opposite to the array $t o p$ (from the last element to the first). For convenience in further processing, we reverse the array $t o p$ .

color.assign(n + 1, -1);
reverse(top.begin(), top.end());

Vertices belonging to the same strongly connected component are assigned the same color. The current color is stored in the variable $с$ .

c = 0;

Next, iterate through the array $t o p$ from left to right and start a depth-first search dfs2 from each vertex that has not yet been colored.

for (int v : top)
  if (color[v] == -1) dfs2(v, c++);

The variable $c$ stores the number of strongly connected components. Iterate over all edges of the original graph $(i, t o)$ .

for (i = 1; i < g.size(); i++)
for (int to : g[i])

Check whether the vertices $i$ and $t o$ belong to different strongly connected components, that is, whether they are colored with different colors. If this is the case, then the edge $(i, t o)$ belongs to the condensation graph, so we add the pair $(co l or [i], co l or [t o])$ (color[i], color[to]) to the set $s$ . Since a set is used rather than a multiset, duplicate pairs are not counted.

  if (color[i] != color[to])
    s.insert(make_pair(color[i], color[to]));

Print the number of edges in the condensation graph.

printf("%d\n",s.size());