Задача №3491. Поиск в ширину--2 (вершины идентифицируются названиями)
Напишите программу, которая будет реализовывать поиск в ширину в простом графе, вершины которого не нумерованы и идентифицируются словесными названиями.
В первой строке входных данных задано число NUM — количество различных поисков в ширину, которые нужно выполнить (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит целое число M — количество ребер графа. Далее следуют M строк, каждая из которых содержит по два названия — концы соответствующего ребра. Названия гарантированно не содержат пробелов и отделены друг от друга одним пробелом. Далее, в последней строке блока, записано единственное название — вершина, начиная с которой нужно запустить поиск (это название гарантированно хоть раз упоминалась как конец одного из ребер).
Количество различных графов в одном тесте NUM не превышает 5, количество рёбер в графе не превышает 50000.
Выведите на стандартный выход (экран) NUM блоков, в каждом из которых записаны расстояния от указанной начальной вершины до всех достижимых (если есть недостижимые вершины, они вообще не упоминаются). Перечень должен быть отсортирован по названиям вершин, каждая пара (название, расстояние) должна выводиться в отдельной строке, блоки должны быть отделены друг от друга строкой «===» (три знака «равно»).
Задачу можно решить, пользуясь map<string,int> и vector<string> для преобразований имен в номера и номеров в имена; тогда внутри программы можно использовать представление графа как vector<vector<int> >. Для вывода в отсортированном порядке использовать прохождение по всем элементам от begin() до end() структуры map<string,int> (превращающей названия в номера).
Другой способ — вообще отказаться от нумерации вершин числами и представлять граф как map<string,vector<string> >; в этом случае массивы, используемые самим поиском, следует заменить на map<string,int>.
2 2 Cherk Zol Cherk Sm Zol 4 A Bb Bb Ccc Ccc A Dddd Eeeee Bb
Cherk 1 Sm 2 Zol 0 === A 1 Bb 0 Ccc 1