SGU 196 – Matrix Multiplication

file

Let us consider an undirected graph G = <V, E> which has N vertices and M edges. Incidence matrix of this graph is an N × M matrix A = {aij}, such that aij is 1 if i-th vertex is one of the ends of j-th edge and 0 in the other case. Your task is to find the sum of all elements of the matrix ATA where AT is A transposed, i.e. an M × N matrix obtained from A by turning its columns to rows and vice versa.

Input

The first line of the input file contains two integer numbers — N and M (2 le N le 10,000, 1 le M le 100,000). 2M integer numbers follow, forming M pairs, each pair describes one edge of the graph. All edges are different and there are no loops (i.e. edge ends are distinct).

Output

Output the only number — the sum requested.

Sample test(s) Input 4 4 1 2 1 3 2 3 2 4 Output 18 给定一个有N个顶点,M条边的图,N M的矩阵A中的元素a(i,j)为1当且仅当第i个顶点是第j条边的端点,否则为零。求A\'A的各个元素之和。

直接计算的话,内存不够,时间也不够(O(N^3)).考虑到最终求的是和,可以用类似POJ 3318 的压缩方法来处理.设A\'A=C, 构造一个全一向量I,最终结果是IA\'A=IC各个元素之和.这样,O(N^2)的时间就可解决,但是在0.5秒之内依然不可能运行一亿次,考虑到矩阵是稀疏的,再观察矩阵构造方法,就可以得到O(M*2)的算法,这里不再叙述,可参考代码.

#include <stdio.h>
int a[10005]={0};
int b[100005][2];
int main()
{
    int n,m;
    int ans=0;
    int x,y,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        b[i][0]=x;
        b[i][1]=y;
        a[x]++;
        a[y]++;
    }

    for(i=1;i<=m;i++)
    {
        ans+=a[b[i][0]]+a[b[i][1]];
    }
    printf("%dn",ans);
    return 0;
}