Количество графов, образованных изменением цвета любого узла красного цвета с черным родителем на черный

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

Для заданного ориентированного графа G , состоящего из N узлов и N-1 ребер, и положительного целого числа K, и изначально все вершины графа красные, кроме K, который является черным, задача состоит в том, чтобы подсчитать количество различных возможных графы, образованные изменением цвета любого узла красного цвета на черный, только если их родитель окрашен в черный цвет, любое количество раз.

Примеры:

Input: N = 5, K = 1, Edges[] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}
Output: 10
Explanation: 
When node 2 is red then we can’t change the color of 4 and 5 because its parent(2) is not black. Therefore, there is only one possible way to color. 

                                        1(B)
                                     /        
                                2(R)          3(R)
                             /        
                         4(R)        5(R)
But when 2 is black, then we can change the color of 4 and 5 (4 and 5 are independent of each other) in 2 possible ways, each(red-black) because its parent(2) is black.

Node 3 again can be colored in 2 different ways. Therefore, the total number of ways of coloring is (5*2 = 10). Thus there are a total of 10 different possible graphs.

Input: N = 3, K = 2, Edges[] = {{1, 2}, {1, 3}}
Output: 1

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

  1. Данный ориентированный граф можно рассматривать как дерево с корнем в узле K. И количество различных возможных графов равно количеству способов соответственно раскрасить граф.
  2. Дети любого узла могут быть окрашены в черный цвет, только если родительский узел окрашен в черный цвет. Следовательно, все узлы от K до текущего узла должны быть окрашены в черный цвет.
  3. Поэтому идея состоит в том, чтобы выполнить обход в глубину из K и для каждого узла либо покрасить текущий узел в черный цвет, либо оставить его как есть. Затем обход поддеревьев только в том случае, если текущий узел окрашен в черный цвет.
  4. Если у текущего узла U 3 дочерних элемента, а X, Y, Z — это количество способов покрасить поддеревья дочерних элементов узла U. Тогда общее количество способов покрасить текущее поддерево равно (X*Y* Я+1). Узел K не может быть окрашен, поэтому 1 не добавляется к узлу K.

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

  • Сформируйте список смежности из заданных ребер графа и сохраните его в переменной, скажем, в графе .
  • Определите рекурсивную функцию, скажем, numOfGraph(U) , где U — текущий узел:
    • Если узел U является листом, верните 2 . Поскольку узел может быть окрашен как в черный, так и в красный цвет.
    • Инициализируйте переменную, скажем, cnt , которая хранит количество способов раскрасить график.
    • Переберите узел, связанный с текущим узлом U, используя переменную i , и выполните следующие шаги:
      • Обновите значение cnt до cnt*NumberOfGraph(i) , рекурсивно вызвав функцию для дочернего узла i .
    • После вышеуказанных шагов верните значение cnt+1.
  • Наконец, вызовите функцию DFS из узла K , т.е. numOfGraph(K) , и выведите возвращаемое ею значение в качестве ответа.

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

Сложность времени: НА)
Вспомогательное пространство: O(1)

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