Теория графов: поиск в ширину
Есть n вершин, соединенных m ребрами. Некоторые вершины особенные, а другие обычные. Существует не более одного пути для перемещения из одной вершины в другую.
Первый запрос:
Мне нужно выяснить, сколько существует пар специальных вершин, которые связаны прямо или косвенно.
Мой подход:
Я буду применять BFS (через очередь), чтобы увидеть, сколько узлов каким-либо образом связаны друг с другом. Пусть число специальных вершин, которые я обнаружу в этом, будет n, тогда ответ на мой запрос будет nC2. Я буду повторять это, пока все вершины не будут. посещены.
Второй запрос:
Сколько вершин лежит на пути между любыми двумя специальными вершинами.
Мой подход:
В моем подходе к запросу 1 я буду применять BFS, чтобы выяснить путь между любыми двумя специальными вершинами, а затем вернуться назад и отметить вершины, лежащие на пути.
Проблема:
Количество вершин может достигать 50000. Таким образом, применяя BFS, а затем, я думаю, возврат будет медленнее из-за моего временного ограничения (2 секунды).
У меня есть список всех вершин и список смежности. Теперь, вставляя вершины в мою очередь, пока BFS, могу ли я как-то вычислить ответ и на запрос 2? Есть ли лучший подход, который можно использовать для решения проблемы? Формат ввода будет таким, что мне сообщат, является ли вершина особенной или нет, а затем мне дадут информацию о i-ом пути, который соединяет две вершины. Существует не более одного пути для перемещения из одной вершины в другую. ,
Решение
Первый запрос решается путем разделения вашего леса на деревья.
Начиная с полного набора вершин, выберите одну, а затем посещайте все узлы, которые можете оттуда, пока не сможете больше посещать вершины. Это одно дерево. Повторите для каждого дерева.
Теперь у вас есть K мешков с вершинами, каждая из которых содержит 0-j специальные. Это отвечает на первый вопрос.
Что касается второго вопроса, я предполагаю, что тривиальным решением действительно является BFS — путь между вершиной к другой для каждой пары в их подграфе.
Вы также можете использовать древовидную природу вашего подграфа. Этот вопрос: Как найти кратчайший простой путь в дереве за линейное время? упоминает это. (Я действительно еще не копался в этом, хотя)
Другие решения
Для первого запроса оптимальным является один раунд BFS и несколько простых вычислений, которые вы описали.
Для второго запроса, предполагая наихудший случай, когда все вершины являются особыми, а граф представляет собой дерево, выполнение BFS для каждого запроса приведет к сложности O (Q | V |), где Q — количество запросов. Вы будете сталкиваться с неприятностями, если Q больше 104 и | V | также больше 104.
В худшем случае мы в основном решаем проблему кратчайшего пути для всех пар, но на дереве / в лесу. Когда | V | мал, мы можем сделать BFS на всех узлах, что приводит к O (| V |2) алгоритм. Однако есть более быстрый алгоритм:
- Прочитайте все запросы второго типа и сохраните все пары в наборе S.
- Для каждого дерева в лесу:
- Выберите корневой узел для текущего дерева. Рассчитайте расстояние от корневого узла до всех других узлов в текущем дереве (независимо от того, является оно особенным или нет).
- Вычисление наименьшего общего предка (LCA) для всех пар запрашиваемых узлов (которые хранятся в наборе S). Это может быть сделано с Тарьяна автономный алгоритм LCA.
- Рассчитайте расстояние между парой узлов:
dist(root, a) + dist(root, b) - dist(root, lca(a,b))
Пусть arr будет массивом bool, где arr [i] равен 1, если он особенный, и 0 в противном случае.
find-set (i) возвращает корневой узел дерева. Таким образом, любые узлы, лежащие в одном и том же дереве, возвращают одно и то же число.
for(int i=1; i<n; i++){
for(int j=i+1; j<=n; j++){
if(arr[i]==1 && arr[j]==1){ //If both are special
if(find-set(i)==find-set(j)){ //and both i and j belong to the same tree
//k++ where k is answer to the first query.
//bfs(i,j) and find the intermediate vertices and do ver[i]=1 for the corresponding intermediate vertex/node.
}
}
}
}
наконец, не считайте 1 в матрице вер, которая является ответом на второй запрос.