1947. Конденсация графа

Для заданного ориентированного графа найдите количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G’, вершинами которого служат компоненты сильной связности G, а дуга в G’ присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

Вход. Первая строка содержит количество вершин n и количество ребер m (n ≤ 10⁴, m ≤ 10⁵) графа. Каждая из следующих m строк содержит описание ребра графа. i-ое ребро описывается номерами начальной b_i и конечной e_i (1 ≤ b_i, e_i ≤ n) вершины. В графе могут присутствовать кратные ребра и петли.

Выход. Выведите количество ребер в конденсации графа.

Пример входа	Пример выхода
4 4 2 1 3 2 2 3 4 3	2

РЕШЕНИЕ

графы – сильная связность

Анализ алгоритма

Находим компоненты сильной связности графа. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет. Пусть color[i] – цвет i-ой вершины. Число цветов окраски равно количеству компонент сильной связности.

Перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра (a, b), для которого color[a] ≠ color[b], занесем во множество s пару (color[a], color[b]). Поскольку мы используем множество, а не мультимножество, то кратные пары учитываться не будут. Количество элементов во множестве s будет равняться числу ребер в конденсации графа.

Пример

Граф, приведенный в примере, имеет следующий вид:

Конденсация графа состоит из трех вершин и двух ребер.

Реализация алгоритма

Входной граф храним в списке смежности g. Обратный граф (граф, в котором изменены все направления ребер) храним списке смежности gr. Ребра конденсированного графа будем сохранять во множестве пар s.

vector<vector<int> > g, gr;

vector<int> used, top, color;

set<pair<int,int> > s;

Функция dfs1 реализует поиск в глубину на входном графе. В массив top заносим последовательность вершин в порядке, в котором поиск в глубину завершает их обработку.

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

if (!used[to]) dfs1(to);

top.push_back(v);

}

Функция dfs2 реализует поиск в глубину на обратном графе. Все вершины, которые будут пройдены в результате рекурсивного вызова функции dfs2, принадлежат одной компоненте сильной связности. Красим все пройденные вершины цветом с.

void dfs2(int v, int c)

{

color[v] = c;

for (int to : gr[v])

if (color[to] == -1) dfs2(to, c);

}

Основная часть программы. Читаем входные данные. Строим обратный граф.

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);

}

Запускаем поиск в глубину на входном графе. Последовательность, в которой завершается обработка вершин графа, сохраняется в массиве top.

used.resize(n+1);

for(i = 1; i <= n; i++)

if (!used[i]) dfs1(i);

Запускаем поиск в глубину на обратном графе. Вершины обратного графа рассматриваем в порядке обхода массива top справа налево (с конца в начало). Для удобства дальнейшей обработки обернем массив top.

color.assign(n + 1, -1);

reverse(top.begin(), top.end());

Вершины, входящие в одну компоненту сильной связности, красим одним и тем же цветом. Текущий цвет раскраски находится в переменной с.

c = 0;

Теперь двигаемся по массиву top слева направо и вызываем из каждой еще непокрашенной вершины поиск в глубину dfs2.

for (int v : top)

if (color[v] == -1) dfs2(v, c++);

Переменная c содержит количество компонент связности. Перебираем все ребра графа (i, to).

for (i = 1; i < g.size(); i++)

for (int to : g[i])

Проверяем, лежат ли вершины i и to в разных сильно связных компонентах. Это так, если они покрашены разными цветами. Тогда ребро (i, to) принадлежит конденсации графа, поэтому заносим во множество s пару (color[i], color[to]). За счет того что мы используем множество, а не мультимножество, то кратные пары учитываться не будут.

if (color[i] != color[to])

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

Выводим количество ребер в конденсации графа.

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

Java реализация

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();

}

}