1947. Condensation
of the graph
Find the number
of edges in the condensation of the given directed graph.
The condensation
of a directed graph G is a directed graph G’, whose vertices correspond to
the strongly connected components of graph G. An edge is added to graph G’ if and only if
there exists at least one edge between vertices belonging to the corresponding
connected components in graph G.
There are no
multiple edges in the condensation graph.
Input. The
first line contains the number of vertices n and the number of edges m (n ≤ 104, m ≤ 105) in the graph. Each of the next m lines describes one edge of the graph. The i-th edge is given by two numbers:
the starting vertex bi and the ending vertex ei (1 ≤ bi,
ei ≤ n). The original graph may
contain multiple edges and self-loops.
Output. Print the number of edges
in the condensation graph.
|
Sample
input |
Sample
output |
4 42 13 22 3
4 3 |
2 |
SOLUTION
graphs – strongly connected
components
Algorithm analysis
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 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 color[a] ≠ color[b], add the pair (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 gr. 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 top 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);
}
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);
}
Start a depth-first search on the input graph. The order
in which vertex processing is completed is stored in the array top.
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
top (from the last element to the first). For convenience in further
processing, we reverse the array top.
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.
c = 0;
Next,
iterate through the array top 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, to).
for (i = 1; i < g.size(); i++)
for (int to : g[i])
Check whether the vertices i and to belong
to different strongly connected components, that is, whether they are colored
with different colors. If this is the case, then the edge (i, to) belongs to
the condensation graph, so we add the pair (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());
Java implementation
import java.util.*;
class Pair implements Comparable<Pair>
{
int x, y;
Pair(int x, int y)
{
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pair a)
{
if (x == a.x) return y - a.y;
return x - a.x;
}
}
public class Main
{
static
ArrayList<Integer>[] g, gr;
static int used[], color[];
static Vector<Integer> top = new
Vector<Integer>();
static TreeSet<Pair> s = new TreeSet<Pair>();
static void dfs1(int v)
{
used[v] = 1;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v].get(i);
if (used[to] == 0) dfs1(to);
}
top.add(v);
}
static void dfs2(int v, int c)
{
color[v] = c;
for(int i = 0; i < gr[v].size(); i++)
{
int to = gr[v].get(i);
if (color[to] == -1) dfs2(to,c);
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
Scanner
con = new Scanner(System.in);
int n = con.nextInt();
int m = con.nextInt();
g = new ArrayList[n+1];
for(int i = 0; i <= n; i++)
g[i] = new ArrayList<Integer>();
gr = new ArrayList[n+1];
for(int i = 0; i <= n; i++)
gr[i] = new ArrayList<Integer>();
for (int i = 0; i < m; i++)
{
int a = con.nextInt();
int b = con.nextInt();
g[a].add(b);
gr[b].add(a);
}
used = new int[n+1];
for(int i = 1; i <= n; i++)
if (used[i] == 0) dfs1(i);
color = new int[n+1];
Arrays.fill(color, -1);
int c = 0;
for(int i = 1; i <= n; i++)
{
int v = top.get(n-i);
if (color[v] == -1) dfs2(v,c++);
}
for(int i = 1; i < g.length; i++)
for(int j = 0; j < g[i].size(); j++)
{
int to = g[i].get(j);
if (color[i] != color[to])
s.add(new Pair(color[i],color[to]));
}
System.out.println(s.size());
con.close();
}
}