Counting Stars

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2657 Accepted Submission(s): 780

Problem Description
Little A is an astronomy lover, and he has found that the sky was so beautiful!

So he is counting stars now!

There are n stars in the sky, and little A has connected them by m non-directional edges.

It is guranteed that no edges connect one star with itself, and every two edges connect different pairs of stars.

Now little A wants to know that how many different "A-Structure"s are there in the sky, can you help him?

An “A-structure” can be seen as a non-directional subgraph G, with a set of four nodes V and a set of five edges E.

If V=(A,B,C,D) and E=(AB,BC,CD,DA,AC), we call G as an “A-structure”.

It is defined that “A-structure” G1=V1+E1 and G2=V2+E2 are same only in the condition that V1=V2 and E1=E2.

Input
There are no more than 300 test cases.

For each test case, there are 2 positive integers n and m in the first line.

2≤n≤105, 1≤m≤min(2×105,n(n−1)2)

And then m lines follow, in each line there are two positive integers u and v, describing that this edge connects node u and node v.

1≤u,v≤n

∑n≤3×105,∑m≤6×105

Output
For each test case, just output one integer–the number of different "A-structure"s in one line.

Sample Input
4 5
1 2
2 3
3 4
4 1
1 3
4 6
1 2
2 3
3 4
4 1
1 3
2 4

Sample Output
1
6

三元环计数问题，我们对每个三元环的边计算数量，然后求组合数即可。

求三元环：

  1. 计算每个点的度。
  2. 点小的连向点大的，如果一样则序号小的连向大的。
  3. 枚举每一条边，若端点的两点能到达同一点则是找到了一个三元环。

总复杂度：m * sqrt(m) .

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,d[N],u[N<<1],v[N<<1],vis[N],cnt[N<<1];
int head[N],nex[N<<1],to[N<<1],tot;
long long res;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot; 
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		tot=0; res=0ll;
		for(int i=1;i<=n;i++)	head[i]=0,d[i]=0;
		for(int i=1;i<=m;i++)	
			scanf("%d %d",&u[i],&v[i]),d[u[i]]++,d[v[i]]++,cnt[i]=0;
		for(int i=1;i<=m;i++){
			if(d[u[i]]<d[v[i]])	add(u[i],v[i]);
			else if(d[u[i]]>d[v[i]]) add(v[i],u[i]);
			else{
				if(u[i]<v[i])	add(u[i],v[i]);
				else	add(v[i],u[i]);
			}
		}
		for(int i=1;i<=m;i++){
			for(int j=head[u[i]];j;j=nex[j])	vis[to[j]]=j;
			for(int j=head[v[i]];j;j=nex[j]){
				if(to[j]==u[i])	continue;
				if(vis[to[j]]){
					cnt[i]++; cnt[j]++; cnt[vis[to[j]]]++;
				}
			}
			for(int j=head[u[i]];j;j=nex[j])	vis[to[j]]=0;
		}
		for(int i=1;i<=m;i++)	if(cnt[i]>1)	res+=1ll*(cnt[i]-1)*cnt[i]/2;
		printf("%lld\n",res);
	}
	return 0;
}