Темы --> Информатика --> Структуры данных --> Система непересекающихся множеств
---> 15 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

 

+

+

(4,3)

+

+


Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

  • закрасить клетку (i,j) в черный цвет.
  • для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.

Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

Входные данные

Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 105), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i N, 1 ≤ j M.

Выходные данные

На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.

Оценка задачи

1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.

Примеры
Входные данные
5 5 6
Color 4 2
Neighbors 4 3
Color 2 3
Color 3 3
Neighbors 4 3
Neighbors 5 1
Выходные данные
3
4
4 1
4 4
3 3
5 3
4
4 1
4 4
1 3
5 3
2
5 2
4 1
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Максимальное время работы на одном тесте: 5 секунд

От вас требуется определить вес минимального остовного дерева для неориентированного взвешенного связного графа.

Входные данные

В первой строке входных данных находятся числа N и M (1 <= N <= 100; 1 <= M <= 6000), где N – количество вершин в графе, а M – количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B – номера вершин, соединённых ребром, а C – вес ребра (натуральное число, не превышающее 30000)

Выходные данные

Вывести одно число – искомый вес.

Примеры
Входные данные
3 3
1 2 1
2 3 2
3 1 3
Выходные данные
3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы острова и порядок строительства мостов между островами (мост соединяет два острова). Необходимо узнать, после строительства какого моста все острова станут связными.

Одно разбросанное на островах Океании государство решило создать сеть автомобильных дорог (вернее, мостов). По каждому мосту можно перемещаться в обе стороны. Был разработан план очередности строительства мостов и известно, что после постройки всех мостов можно будет проехать по ним с каждого острова на каждый (возможно, через некоторые промежуточные острова).

Однако, этот момент может наступить до того, как будут построены все мосты. Ваша задача состоит такое минимальное количество мостов, после постройки которых (в порядке строительства по плану) можно будет попасть с любого острова на любой другой.

Входные данные

Первая строка содержит два числа: N - число островов (1 ≤ N ≤ 100 000) и M – количество мостов в плане (1 ≤ M ≤ 200 000). В каждой следующей строке содержится описание моста – два числа x и y (0 ≤ x, y < N) – номера соединяемых островов.

Выходные данные

Выведите в выходной файл одно число – минимальное количество построенных мостов, по которым можно попасть с любого острова на любой.

Примеры
Входные данные
4 5
0 1
0 2
1 2
2 3
3 0
Выходные данные
4
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Одно разбросанное на островах Океании государство решило создать сеть автомобильных дорог (вернее, мостов). По каждому мосту можно перемещаться в обе стороны. Был разработан план очередности строительства мостов и известно, что после постройки всех мостов можно будет проехать по ним с каждого острова на каждый (возможно, через некоторые промежуточные острова

Однако, этот момент может наступить до того, как будут построены все мосты. Вам необходимо определить такое минимальное количество мостов, после строительства которых (в порядке, определенном планом), можно будет попасть с любого острова на любой другой.

Входные данные

Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.

Выходные данные

Программа должна вывести единственное число - минимальное количество построенных мостов, после которого можно будет попасть с любого острова на любой другой.

Примеры
Входные данные
4 5
1 2
1 3
2 3
3 4
4 1
Выходные данные
4
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

В неориентированный взвешанный граф добавляют ребра. Напишите программу, которая в некоторые моменты находит сумму весов ребер в компоненте связности.

Входные данные

В первой строке записано два числа n и m (1≤n,m≤106) - количество вершин в графе и количество производимых добавлений и запросов. Далее следует m строк с описанием добавления или запроса. Каждая строка состоит из двух или четырех чисел. Первое из чисел обозначает код операции. Если первое число 1, то за ним следует еще три числа x, y, w. Это означает, что в граф добавляется ребро из вершины x в вершину y веса w. (1≤x<y≤n, 1≤w≤103). Кратные ребра допустимы. Если первое число 2, то за ним следует ровно одно число x. Это означает, что необходимо ответить на вопрос, какова сумма ребер в компоненте связности, которой принадлежит вершина x (1≤x≤n).

Выходные данные

Для каждой операции с кодом 2 выведите ответ на поставленную задачу. Ответ на каждый запрос выводите на отдельной строке.

Примеры
Входные данные
6 10
2 1
1 1 2 1
2 1
1 2 4 2
2 1
1 1 4 3
2 1
1 3 5 3
2 5
2 6
Выходные данные
0
1
3
6
3
0

Страница: 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест