Задача №3490. Динамический мультиграф
Пусть нужно иметь дело с невзвешенным неориентированным мультиграфом, в котором много вершин и не очень много ребер. Причем, для полного счастья этот мультиграф динамический, то есть изменяется со временем: иногда приходят запросы «добавить ребро между вершинами v[i] и v[j]» (если уже есть — добавить еще одно, на то и мультиграф) или «удалить ребро между вершинами v[i] и v[j]» (если ребер несколько — должно стать на одно меньше, если одно — должно не стать, если и так не было — граф остается неизменным, ибо даже мультиграф не может содержать отрицательное количество ребер).
Раз вершин много — однозначно нельзя пользоваться матрицей смежности, а надо пользоваться некоторым аналогом списков смежности. Но если из некоторых вершин может выходить по много ребер, то при реализации списков смежности как vector<list<int> > или как vector<vector<int> > операция удаления ребер будет слишком медленной, поскольку потребует просмотра всего списка или вектора. Поэтому в такой ситуации может быть целесообразной реализация через vector<multiset<int> >: 0-ой элемент вектора содержит мультимножество всех тех вершин, куда идут ребра из v[0], 1-ый — мультимножество вершин, куда идут ребра из v[1], и т. д.
Напишите программу, которая будет обрабатывать последовательность запросов перечисленных видов, представляя неориентированный невзвешенный мультиграф как vector<multiset<int> >.
RESET_GRAPH num — создать новый граф, содержащий num вершин (с 0-й по (num–1)-ую) и не содержащий ни одного ребра. Если перед этим уже хранился некий граф, он уничтожается. Действие происходит только с данными в памяти, на экран ничего не выводится.
ADD j k — добавить к неориентированному мультиграфу ребро {v[j], v[k]}. Действие происходит только с данными в памяти, на экран ничего не выводится.
DEL j k — изъять из неориентированного мультиграфа ребро {v[j], v[k]}. Если это возможно, то есть между этими вершинами есть хотя бы одно ребро, то действие происходит только с данными в памяти, на экран ничего не выводится. Если это невозможно, то есть между этими вершинами нет ни одного ребра, на экран выводится сообщение "CNNT" (большими буквами, сокращенно от "CANNOT"), а данные в памяти не изменяются.
CHK j k — проверить, существует ли ребро, соединяющее вершины v[j] и v[k]. Надо вывести на экран большую латинскую букву "Y" или "N" (сокращенно от "YES" / "NO"); данные в памяти при этом не изменяются.
CHECK_PATH j k — проверить, существует ли путь произвольной длины, соединяющий вершины v[j] и v[k]. Надо вывести на экран слово "YES" или "NO" (большими буквами); данные в памяти при этом не изменяются.
Во входных данных записана последовательность запросов RESET_GRAPH, ADD, DEL, CHK и CHECK_PATH — каждый в отдельной строке, согласно вышеописанному формату. Первым гарантированно идет RESET_GRAPH, далее порядок запросов произвольный. При каждом запросе ADD, DEL, CHK или CHECK_PATH указываются два разных номера вершин от 0 до num–1, где num — количество вершин текущего графа (согласно последнему выполненному запросу RESET_GRAPH). Количество запросов нигде не указано, данные следует читать до конца файла.
Суммарное количество запросов ADD, DEL и CHK может достигать 200000, а суммарное количество запросов RESET_GRAPH и CHECK_PATH не превышает 30. Количество вершин в графе не превышает 100000.
Выведите на стандартный выход (экран) сообщения согласно описанным в форматах запросов правил. Каждое сообщение следует выводить в отдельной строке.
В первом тесте, ответ «N» выдается на запрос «CHK 0 2», «YES» — на запрос «CHECK_PATH 0 2», «CNNT» — на второй из запросов «DEL 1 2», «NO» — на последний из запросов «CHECK_PATH 0 2».
RESET_GRAPH 3 ADD 0 1 ADD 0 1 ADD 1 2 CHK 0 2 CHECK_PATH 0 2 DEL 1 2 DEL 1 2 ADD 0 2 RESET_GRAPH 7 CHECK_PATH 0 2
N YES CNNT NO
RESET_GRAPH 2 ADD 0 1 ADD 1 0 CHK 0 1 DEL 0 1 CHK 0 1 DEL 0 1 CHK 0 1 DEL 0 1
Y Y N CNNT