eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

Giriş verilənləri

Первая строка содержит количество вершин n и количество ребер m (n10^4, m10^5) графа. Каждая из следующих m строк содержит описание ребра графа. i-ое ребро описывается номерами начальной b[i] и конечной e[i] (1b[i], e[i]n) вершины. В графе могут присутствовать кратные ребра и петли.

Çıxış verilənləri

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

prb1947.gif

Nümunə

Giriş verilənləri #1
4 4
2 1
3 2
2 3
4 3
Çıxış verilənləri #1
2
Müəllif Виталий Гольдштейн
Mənbə Зимняя школа, Харьков 2011, День 9