Минимизируйте цвета, чтобы нарисовать график так, чтобы ни один путь не имел одного цвета

Опубликовано: 19 Сентября, 2022

Дан ориентированный граф с N узлами и M соединениями, показанными в матрице mat[] , где каждый элемент имеет вид {x i , y i }, обозначающий направленное ребро от y i до x i . Задача состоит в том, чтобы использовать минимальное количество цветов, чтобы раскрасить узлы графа так, чтобы никакие два узла на пути не были одного цвета.

Примеры:

Input: N = 5, M = 6, mat = {{1, 3},  {2, 3},  {3, 4}, {1, 4},  {2, 5},  {3, 5}}
Output: 3
Explanation: The graph nodes can be coloured as shown below
and that is the minimum number of colours possible.
 

Example 1

Input: N = 3, M = 2, mat = {{1, 3}, {2, 3}}
Output: 2
Explanation: Here 1 and 2 can be assigned same colour and 3 another colour.

Подход: Задача может быть решена с использованием концепции топологической сортировки следующим образом:

We can observe that the minimum number of colours required is the same as the length of the longest path of the graph.

All nodes having indegree = 0 can be assigned the same colour. Now remove one indegree from their neighbours and again iterate all the nodes with indegree = 0.

If this is followed, a node will be assigned a colour only when all the other nodes above it in all the paths are assigned a colour. So this will give the maximum length of  a path.

Выполните следующие шаги, чтобы реализовать идею:

  • Создавать список смежности ориентированного графа с заданными ребрами.
  • Поддерживайте вектор степени входа для хранения степени входа каждого узла.
  • Объявите переменную (например, lvl ) для хранения глубины узла.
  • Во время каждой итерации топологической сортировки берется новый цвет и назначается миньонам со степенью вхождения 0 , и на каждой итерации уровень увеличивается на единицу по мере взятия нового цвета.
  • Верните окончательное значение lvl в качестве требуемого ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N + M)
Вспомогательное пространство: O(N + M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ