Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S.
Расстояние между вершинами A и B это длина кратчайшего пути из A в B.
Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S,
выведите их в произвольном порядке.
Формат входного файла
Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины.
Вершины пронумерованы целыми числами от 1 до N.
Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.
Формат выходного файла
Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S.
Если какая-то из вершин недостижима из S, выведите единственное число −1.
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
You are to write a program that performs a topological sorting of a directed graph.
Graph contains N vertices, numbered with integers from 1 to N, and M edges.
In other words, given a partial order on numbers from 1 to N,
your program must produce some linear order on these numbers
which does not conflict with the given partial order.
Input file format
Input file contains two integers N and M, followed by M pairs of integers.
Integers in each pair are different, and represent starting and ending vertex of a graph edge.
These pairs may also be considered comparisons where the first number precedes
the second one.
Output file format
Output file must contain a permutation of integers from 1 to N —
numbers of vertices sorted in topological order.
(That is, representing a linear order.)
If ordering is not possible, output file must contain a single number −1.
Вам задан связный ориентированный граф с N вершинами и M ребрами.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Формат входного файла
Граф задан во входном файле следующим образом: первая строка содержит числа N и M.
Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до
N - номера начала и конца ребра.
Формат выходного файла
На первой строке выведите число K - количество компонент сильной связности в заданном графе.
На следующей строке выведите N чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
