Найти критические ребра MST: возможно с модифицированным алгоритмом Прима?

Я сталкивался с этим вопросом, когда находил решение проблемы «критического края». Исходная (C ++) проблема, которую я уже решил, была:

Рассмотрим граф G = (V, E). Найдите, сколько ребер принадлежит все MSTs, сколько ребер делают не принадлежать любой MST и сколько ребер принадлежат некоторым MST, но не всем.

Давайте назовем «зелёный», «красный» и «жёлтый» соответственно ребрами в 3 вышеописанных случаях.

Проведя свое исследование, я наткнулся Найти все критические ребра MST, которая решает проблему. Можно было бы запустить модифицированную версию алгоритма Крускала: если два или более ребер одинакового веса соединяют одни и те же компоненты, образуя цикл, то все это желтые ребра, то есть ребра, которые могут быть включены в MST (или нет) , Ребра, которые были неоспоримо выбраны являются «зелеными» и края, которые создают цикл в одной компоненте, «красные». Итак, оригинальная проблема была решена.

Проблема с приведенным выше алгоритмом заключается в том, что он работает в O (| E | * log | V |), время выполнения алгоритма Крускала (поправьте меня, если я ошибаюсь). Я думал о том, можно ли также использовать модифицированную версию алгоритма Прима, поскольку она имеет более высокую амортизированную сложность: O (| E | + | V | log | V |), если используется куча Фибоначчи.

Мне кажется, что модифицированную версию алгоритма Прима нельзя использовать здесь, так как мы обязаны перебирать все ребра, основываясь на возрастающем весе; Однако я не могу доказать это. Итак, можно ли еще уменьшить сложность этой проблемы?