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
三元环计数问题，我们对每个三元环的边计算数量，然后求组合数即可。
求三元环：
计算每个点的度。点小的连向点大的，如果一样则序号小的连向大的。枚举每一条边，若端点的两点能到达同一点则是找到了一个三元环。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; }