algorithm - 无向图中的三角形计数

Question

我在一次采访中被问及这个问题，并被告知 O(n^2) 是可能的。有人对此有简单的方法吗？

在这里找到一篇论文告诉我它和矩阵乘法一样难: http://kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Answer 1

http://en.wikipedia.org/wiki/Triangle-free_graph

测试一个图是否没有三角形可以通过该问题的解决方案来解决。 O(n^2) 应该是面试官的错误。