Поиск транспонированного графа
Дан ориентированный граф с
v вершинами и e рёбрами; ваша задача — найти его транспонирование.Транспонирование ориентированного графа — это граф, в котором направление всех рёбер исходного графа обращено в противоположную сторону. Другими словами, если в исходном графе есть дуга из
v1 в v2, то в транспонированном графе будет дуга из v2 в v1.
Транспонированный граф полезен для поиска обратных путей или инверсных отношений в исходном графе. Позже в курсе мы рассмотрим некоторые его применения.
Входные данные
В первой строке входа содержатся два целых числа
v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).В следующих
e строках приводятся пары чисел v1, v2 (1 ≤ v1, v2 ≤ v), указывающие, что из вершины v1 есть дуга в вершину v2.Выходные данные
Программа должна вывести список смежности для транспонированного графа. Каждая строка должна начинаться с идентификатора вершины, за которым следует двоеточие (
:), а затем перечисляются все связанные с ней вершины. В отдельных строках связи разделяются пробелом. Порядок самих вершин и их связей может быть произвольным.Примеры
Входные данные | Выходные данные |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB