Как получить треугольник из полного графа без использования матрицы смежности DFS?

Question

Вы можете думать, что зеленый = 1 и синий = 0, это то же самое, что и взвешенная матрица смежности.

Я решаю найти одноцветный треугольник, это треугольник с ребрами, и у каждого ребра одинаковая степень, поэтому есть весовой коэффициент от цифры 1 до цифры 2.

Мы можем найти с помощью этого треугольника с помощью алгоритма DFS, но он требует O (n ^ 2) - потому что это полный граф. Я хочу сделать немного сложнее времени. Можно ли использовать матрицу?

Answer 1

Рассмотрим только верхнюю левую подматрицу 6x6, в которой гарантированно содержит монохроматический треугольник.O (1).