Блог

Есть Вопрос, который у меня возник во время конкурса, но я не смог его решить. Вопрос:

Задан неориентированный граф, имеющий N вершины и M ребер. Каждое ребро окрашено в один из цветов из набора {1,...C} . Существуют q запросы в виде пары целых чисел x и y . Для данного запроса найдите количество различных цветов , которые являются present on each simple path from vertex to vertex .

Ввод:

 5 4 4  // N,M,C
1 2 2  // U and V Nodes have Colour C
1 3 1
2 4 2
4 5 3
5      // Q
4 1    // X,Y
5 4
5 2
2 3
5 4
  

Вывод:

 1
1
2
2
1
  

Для третьего запроса существует только один путь от вершины 5 до 5vertex , который равен {5,4,2}, который содержит два разных цвета, то есть {3,2} .

Как решить этот вопрос с полной постановкой задачи? Ограничивает:

 1<C<40
N and M are in order 10^5
  

Цвет C присутствует на каждом простом пути от u к v тогда и только тогда, когда:

1. Существует путь между u и v .

2. На графике нет пути между u и v , где удалены все цветные ребра C . (Доказательство: если в графе нет пути без ребер этого цвета, каждый путь от u до v в исходном графике содержит по крайней мере одно ребро этого цвета. И наоборот, если каждый простой путь содержит ребро определенного цвета, его удаление явно разъединит эти две вершины).

Это наблюдение приводит к следующему решению:

1. Найдите связанные компоненты в исходном графике (используя, например, поиск в глубину).

2. Для каждого цвета 1 <= c <= C удалите все границы цвета c и найдите связанные компоненты в новом графике.

3. Если x и y находятся в разных компонентах исходного графика, ответ на (x, y) запрос равен 0. В противном случае, это равно количеству таких цветов, c которые x и y находятся в разных компонентах на графике без краев цвета c .

Временная сложность составляет O((N M) * (C 1) Q * C) (первый член соответствует C 1 поиску в глубину. Второй соответствует итерации по всем цветам для каждого запроса).