Problem A. Topological sorting

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

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.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

Задача B. Лабиринт

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

Формат входного файла

Во первой строке входного файла содержатся числа N, x0, y0, x1, y1. Далее следуют N строк по N символов в каждой — описание лабиринта.

Формат выходного файла

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

0 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 1 4 1
..#.
..#.
..#.
....
9

Problem C. Biconnectivity

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 6
1 2
1 3
2 3
1 4
1 5
4 5
1 1

Задача D. Быстрый Дейкстра

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вам необходимо написать программу, которая получает взвешенный ориентированный граф и находит в нем расстояния от вершины S до всех остальных вершин. Расстояние от вершины S до некоторой вершины W — это минимальная длина пути из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.

Формат входного файла

Входной файл содержит три числа N, M и S. Вершины занумерованы целыми числами от 1 до N. S — это номер начальной вершины. M — это количество рёбер. Каждая из следующих M строк содержит три числа — номера начальной и конечной вершин текущего ребра и его вес соответственно. Все веса положительны. Между двумя вершинами может быть максимум одно ребро в каждом направлении.

Формат выходного файла

Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для для них должно быть выведено 1.

Ограничения

1 ≤ N, M ≤ 100000 Все веса меньше или равны 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

0.130s 0.012s 19