• 如果喜欢本站，您可以按CTRL+D收藏本站，方便下次访问。

• 欢迎来自五湖四海的朋友，期待为您分享有价值的资源

# SGU 196 – Matrix Multiplication

10年前 (2010-09-01) 207次浏览

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的各个元素之和。

#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;
}

====
• 版权声明

本站的文章和资源来自互联网或者站长的原创，按照 CC BY-NC-SA 4.0 CN协议发布和共享，转载或引用本站文章应保留来源网址，并遵循相同协议。如果有侵犯版权的资源请尽快联系站长，我们会在24H内删除有争议的资源。
• 网站驱动

• 友情链接

• 支持一下