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.
You are to write a program that receives a connected undirected graph and finds
all its articulation points, which are the vertices that, if removed,
leave disconnected graph.
Input file format
Input file contains two integers N and M.
Vertices are numbered with integer numbers from 1 to N.
M is the number of edges.
Each of next M lines contain pair of integers — numbers of vertices
connected by an edge. There are no pairs of equal numbers.
Output file format
Output file must contain integer representing a quantity of articulation
points, followed by numbers of corresponding vertices in arbitrary order.
Вам необходимо написать программу, которая получает взвешенный ориентированный
граф и находит в нем расстояния от вершины S до всех остальных вершин.
Расстояние от вершины S до некоторой вершины W — это минимальная длина пути
из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.
Формат входного файла
Входной файл содержит три числа N, M и S.
Вершины занумерованы целыми числами от 1 до N. S — это номер начальной
вершины. M — это количество рёбер. Каждая из следующих M строк содержит
три числа — номера начальной и конечной вершин текущего ребра и его вес
соответственно. Все веса положительны. Между двумя вершинами может быть
максимум одно ребро в каждом направлении.
Формат выходного файла
Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние
от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для
для них должно быть выведено −1.
