images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 19:50:49

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

157. Иллюминация

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Боб решил украсить дом иллюминацией. Он соединил проводами несколько ламп и подключил их к электросети. Затем Боб повернул рубильник, но некоторые лампы не загорелись.
Напишите программу, которая определит, используя информацию о выполненных соединениях, какие лампы будут гореть. Лампа будет гореть, если существует путь проходящий через лампу от одного контакта электросети до другого такой, что две части пути к лампе и обратно не имеют общих вершин или вершин, соединенных между собой проводами без нагрузки в виде других ламп.
В первой строке ввода содержатся два целых числа, разделенных пробелом – количество ламп `N\ (1≤N≤100)` и количество проводов `K\ (1≤K≤1000)`. Далее следует `K` строк, в каждой строке сначала указывается номер элемента (0 для электросети, от 1 до `N` для лампы), к которому был присоединен один из концов провода, потом через пробел – номер контакта 1 или 2 (все элементы имеют два контакта), затем указывается элемент и контакт, к которому был присоединен другой конец провода, в том же формате.
В выходной файл в первой строке вывести `N` целых чисел, разделяя их пробелами – если `i`-ая лампа будет гореть, то `i`-ое число должно быть равно 1, иначе 0.

Пример ввода

3 4
0 1 1 1
1 2 2 1
2 2 0 2
1 2 0 2

Вывод для примера

1 0 0
loading