You are to write a program that receives an unweighted undirected graph and writes all its vertices in
order of increasing distance from given vertex S.
Distance between vertices A and B is the length of the shortest path from A to B.
If there are several vertices such that their distances to S are equal,
they may be printed in arbitrary order.
Input file format
Input file contains three integers N, M and S, where M is the number of edges,
S is the starting vertex.
Vertices are numbered with integer numbers from 1 to N.
Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.
Output file format
Output file must contain sequence of vertex numbers sorted by increasing distance from S.
If some vertex is not reachable from S, output a single number −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 чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
