Как эффективно узнать какие вершины соединенные с вершиной A соединены ребром?

Question

[dalbio]

Есть вершина A с ней соединены другие вершины. Моя задача узнать количество пар вершин, которые соединены с вершиной A и соединены между собой. Можно ли это сделать без полного перебора за время n*(n-1), где n-количество вершин соединенных ребром с A?

Comments

[Антон Жилин]

Может, нужно найти число вершин, до которых можно добраться из A?

Answer 1

[Wataru]

В такой постановке - вряд ли есть что либо эффективнее наивного перебора матрицы смежности или списков инцедентности.

Однако, скорее всего вам не надо считать это количество для одной заданной вершины, а просуммировать по всем (задача вроде - найти сколько в графе треугольников).

В таком случае есть более эффективное решение (хоть и с такой же кубической асимптотикой). Суть в том, чтобы перебирать не вершину треугольника, а ребро. Тогда вопрос будет подсчитать, сколько вершин связанны с заданными двумя. Что равносильно: Найти в скольких столбцах матрицы смежности стоят единицы в двух заданных строках. Это линейный проход, но его можно в 64 раза ускорить, если использовать битовое сжатие. Храните матрицу смежности в битах 64-битных чисел. Т.е. один столбец long long матрицы будет отвечать за 64 столбца. В таком виде можно с-AND'ить два числа и потом подсчитать, сколько в числе единичных бит (что тоже можно сделать сильно быстрее, чем за 64 операции).