C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 7236K, 提交时间: 2022-09-06 19:43:11

#include <bits/stdc++.h>

using namespace std;

#define N 100010
#define M 200010

int n, m, U[M], V[M], d[N];
vector <int> e[N];
bool vis[N];
long long ans;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", U + i, V + i);
        ++d[U[i]], ++d[V[i]];
    }
    for (int i = 1; i <= m; ++i) {
        if (U[i] > V[i]) swap(U[i], V[i]);
        if (d[U[i]] < d[V[i]]) e[V[i]].push_back(U[i]);
        else e[U[i]].push_back(V[i]);
    }
    for (int u = 1; u <= n; ++u) {
        for (int v : e[u]) vis[v] = true;
        for (int v : e[u])
            for (int w : e[v])
                if (vis[w]) ++ans;
        for (int v : e[u]) vis[v] = false;
    }
    printf("%lld\n", ans);
    
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 98ms, 内存消耗: 9908K, 提交时间: 2022-09-08 16:41:58

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int d[N],x[N],y[N];
vector<int>a[N];
int v[N];
int main()
{
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i];
		d[x[i]]++,d[y[i]]++;	
	}
	for(int i=1;i<=m;i++)
		if(d[x[i]]==d[y[i]])x[i]>y[i]?a[x[i]].push_back(y[i]):a[y[i]].push_back(x[i]);
		else d[x[i]]>d[y[i]]?a[x[i]].push_back(y[i]):a[y[i]].push_back(x[i]);
	for(int i=1;i<=n;i++)
	{
		for(auto j:a[i])v[j]=i;
		for(auto j:a[i])
			for(auto k:a[j])
				if(v[k]==i)ans++;
	}	
	cout<<ans;
	return 0;
}