Counting Stars

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 129    Accepted Submission(s): 27 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   Source 2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）  

题意 ： 给出一个图，定义一个形状叫做A形状，它表示的是由两个公用一条边的三元环组成的形状，问你图中有几个三元环。

思路 ：对于三元环，可以暴力求，首先枚举每个点a，然后把与它相连的点建立联系，然后再去枚举与它相连的一个点b，此时我们固定点a和点b。

然后得先判断b点的度多不多   设 num = sqrt(m) 度数去与num 比较 （因为形成完全图的时候每个点的度差不多就是 sqrt(m),所以最坏情况就是 sqrt(m) )

1.如果度不多，可以去枚举与b相连的点 c ，看c与a是否有联系有的话就形成一个三元环。

2.如果b点的度很多的话，那么就去枚举 与 a相连的点c，看点c与与点b是否相连，如果相连就建立成一个三元环。

如果不区分度的多少，全都只去枚举b或者只枚举a都会超时。

然后记录下 固定点a 和点 b 时候的三元环个数 sum。 由于此时的三元环都是公用一边的，所以每两个三元环就可以组成一个A形状，两两组合种数就是  sum * (sum - 1) / 2

然后统计 A形状个数就可以了

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> using namespace std; #define ll long long #define maxn 100005 vector<int> G[maxn]; set<ll> st; int vis[maxn],link[maxn],du[maxn]; int main(){ ll ans,sum; int n,m,k,x,y,z,num; while(scanf("%d %d",&n,&m) != EOF){ num = sqrt(m); //作为判断度数多少的标准 st.clear(); for(int i = 1;i <= n;i++){ G[i].clear(); vis[i] = du[i] = link[i] = 0; } for(int i = 1;i <= m;i++){ scanf("%d %d",&x,&y); G[x].push_back(y); G[y].push_back(x); du[x]++; //记录每个点的度 du[y]++; st.insert((ll)x * n + y); //用来记录该边的存在 st.insert((ll)y * n + x); } ans = 0; for(int i = 1;i <= n;i++){ x = i; vis[x] = 1; for(int j = 0;j < G[x].size();j++){ link[G[x][j]] = x; //把与x点有连接的点建立联系 } for(int j = 0;j < G[x].size();j++){ sum = 0; y = G[x][j]; if(vis[y]) continue; if(du[y] <= num){ //如果 y 点的其他分支不多的话，就从 y点去找其他点 for(int k = 0;k < G[y].size();k++){ z = G[y][k]; if(link[z] == x) // 第三个点与第一个点有联系，形成一个三元环 sum++; } }else{ // 否则就从x点去找其他点匹配 ，可以节省时间 for(int k = 0;k < G[x].size();k++){ z = G[x][k]; if(st.find((ll)z * n + y) != st.end()) //第三个点与第二个点之间有联系，形成三元环 sum++; } } //每次取完三元环要去计算有多少个两两组成的 A形状 //当前固定了 x 点和 y 点，剩下的点组成三元环后，两两都能组成一个 A形状，所以A形状个数增加 sum * (sum - 1) / 2 ans += sum * (sum - 1) / 2; } } printf("%lld\n",ans); } return 0; }