图计算
时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0
题目描述
一个(有向或无向)图包含n个顶点和m条不同的边,m<n2。图的边以流的形式给出,流中的每个元素代表一条边,用一对点表示成形如 ( i , j ) 的形式。m条不同边中的每条边都可以在流中多次出现,没有边会缺失。用d表示顶点i的不同的邻居的数目。目标是近似M2=∑i(di)^2 。M2的概念类似于F2,关键的差别是,M2仅仅计数新的与众不同的元素(未出现过的)。
提示使用空间亚线性算法实现。