算法: 如何计算两个如何计算两个节点的共节点？

Question

• 节点之间用边相连如何计算两个节点都相连的节点数？

• 知道用igraph可以算一个节点有多少度，可以算共节点数吗？

数据集：
25 31
25 95
96 24
96 97
96 2
96 98
96 27
96 99
96 100
19 99
19 88
表示相连关系

Answer 1

设n个点，m条边。朴素算法是O(d[u]+d[v])枚举两个点的出边，用一个大小为n的数组记一下每个点与两个点中的几个有边。如果n不大可以压位O(m+n^2/32)预处理O(n/32)查询。