題干：

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)V=(A,B,C,D)?and?E=(AB,BC,CD,DA,AC)E=(AB,BC,CD,DA,AC), we call G as an "A-structure".?

It is defined that "A-structure"?G1=V1+E1G1=V1+E1?and?G2=V2+E2G2=V2+E2?are same only in the condition that?V1=V2V1=V2?and?E1=E2E1=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≤1052≤n≤105,?1≤m≤min(2×105,n(n?1)2)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≤n1≤u,v≤n?

∑n≤3×105∑n≤3×105,∑m≤6×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

題目大意：

????

解題報告：

暴力。這題主要是卡空間了啊不然隨便搞的。。然后卡空間了變成怎么交都MLE、、、

對于題干，不難想到就是問有多少個雙三元環，所有我們枚舉每一條邊，然后能構成的所有三元環個數假設x，那就是C(2,x)就是這條邊的貢獻。

暴力每個點i，然后枚舉他的所有邊獲得點j，然后對于第三個點k分兩種情況討論：

①如果j的臨邊數目少于，那么直接暴力就好，復雜度。

②如果臨邊數目大于，（這樣的點一定不會多于的復雜度? 個）那么暴力i的鄰接點，二分判斷有沒有就可以了。

這樣保證總復雜度。

好像還有更優秀的做法：參考博客

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int e[MAX]; int n,m; int main() {while(~scanf("%d%d",&n,&m)) {for(int i = 1; i<=n; i++) e[i] = -1,vv[i].clear();for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);if(u>v) swap(u,v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) sort(vv[i].begin(),vv[i].end());int SQRT = sqrt(m);ll ans = 0;for(int i = 1; i<=n; i++) {for(auto j : vv[i]) e[j] = i;for(auto j : vv[i]) {if(j > i) {int sz = vv[j].size(),cnt = 0;if(sz <= SQRT) {for(auto k : vv[j]) cnt += e[k] == i;}else { for(auto k : vv[i]) cnt += binary_search(vv[k].begin(),vv[k].end(),j); }ans += 1LL*cnt*(cnt-1)/2;}}}printf("%lld\n",ans);}return 0 ; }

還有一個問題啊、、為什么sz<SQRT的話，就一直報TLE啊？？？？歡迎來討論、、、

• 焦作 L
• Commet oj的一道題
• 牛客多校第三場A

改成嚴格的msqrtm的算法：（建有向邊）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int cnt[MAX]; int U[MAX],V[MAX],du[MAX]; vector<PII> vv[MAX]; PII e[MAX]; int n,m; int main() {while(~scanf("%d%d",&n,&m)) {for(int i = 1; i<=n; i++) du[i] = 0,e[i].FF = 0,vv[i].clear();for(int i = 1; i<=m; i++) cnt[i] = 0;for(int i = 1; i<=m; i++) scanf("%d%d",U+i,V+i),du[U[i]]++,du[V[i]]++;for(int u,v,i = 1; i<=m; i++) {u = U[i],v = V[i];if(du[u] > du[v]) vv[v].pb(pm(u,i));else if(du[u] < du[v]) vv[u].pb(pm(v,i));else {if(u<v) vv[u].pb(pm(v,i));else vv[v].pb(pm(u,i)); }}for(int u,v,i = 1; i<=m; i++) {u = U[i],v = V[i];for(auto x : vv[u]) e[x.FF] = pm(i,x.SS);for(auto x : vv[v]) {if(e[x.FF].FF == i) cnt[i]++,cnt[x.SS]++,cnt[e[x.FF].SS]++;} }ll ans = 0;for(int i = 1; i<=m; i++) ans += 1LL*cnt[i]*(cnt[i]-1)/2;printf("%lld\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 6184】Counting Stars（三元环计数，二分，优化暴力，O(m*sqrt(m))，图论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。