Задача A. Бюрократия
Условие
В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата.
Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями
ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить
определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник.
Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для
каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого.
Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы
гарантировала, что никто из них ему не откажет.
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника
с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
Формат входного файла
Входной файл содержит числа
N и
M - количество чиновников и "условий" соответственно.
Далее следуют
M пар целых чисел
(ai, bi), каждая из которых обозначает, что для посещения чиновника с
номером
bi нужно иметь справку от чиновника с номером
ai. Пар, состоящих из двух одинаковых чисел, нет.
Формат выходного файла
Выведите в выходной файл
N целых чисел - одну из возможных последовательностей посещения чиновников.
Если такой последовательности не существует (бывает же и такое!), выведите
−1.
Ограничения
1 ≤ N ≤ 100000;
0 ≤ M ≤ 100000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 3
1 2
1 3
3 4
|
1 3 2 4
|
Задача B. Репликация
Условие
Компьютерная сеть крупного предприятия содержит N серверов баз данных.
Некоторые сервера напрямую связаны между собой кабелями локальной сети, при этом
от каждого сервера можно добраться по связям до любого другого.
Сервера содержат копии одной и той же базы данных. Чтобы поддерживать
эти копии в одинаковом состоянии, используется система репликации — сервер
рассылает каждое изменение, внесённое в его данные, всем соседним серверам,
те, в свою очередь, рассылают его далее до тех пор, пока об изменении не будет оповещена вся сеть.
С целью снижения нагрузки на сеть было решено для некоторых кабелей
разрешить передачу данных только в одном из направлений.
Требуется написать программу, которая по описанию сети зафиксирует направление
передачи по как можно большему числу кабелей таким образом,
чтобы данные по-прежнему можно было передать с любого сервера на любой другой.
Рекомендуется рассмотреть частичные решения
Формат входного файла
Во входном файле содержатся числа
N M, где
N — число серверов,
M — число кабелей.
За ними идут
M пар чисел
ai bi, — номера серверов, соединённых
i-м кабелем.
Сервер не может быть соединён сам с собой,
но два сервера могут быть соединены несколькими кабелями.
Формат выходного файла
В выходном файле должно содержаться
M чисел
di, равных
0,
1 или
2.
di = 0 означает, что для соответствующего кабеля следует сохранить двустороннюю передачу данных,
di = 1 — что следует фиксировать направление от
ai к
bi,
di = 2 — что следует фиксировать направление от
bi к
ai.
Если имеется несколько оптимальных решений, следует вывести любое из них.
Ограничения
1 ≤ N ≤ 2 × 105; 0 ≤ M ≤ 2 × 105
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 3
1 2
1 2
2 3
|
2
1
0
|
| 2 |
3 3
1 2
1 3
2 3
|
1
2
1
|
Problem C. Biconnectivity
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
|
