求估一下时间复杂度
查看原帖
求估一下时间复杂度
1001535
封禁用户楼主2024/8/28 15:15

是 O(nm)\mathcal O(nm) 的吗?

#include <bits/stdc++.h>
using namespace std;
int n, m;
int g;
int ans;
int u[100001], v[100001], w[1000001];
unordered_map<int , unordered_map < int , unordered_map <int , int>>> mp;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i] >> w[i];
	    mp[u[i]][v[i]][w[i]] = 1;
	}
	for (int  i = 1; i <= m; i ++) {
	    int a = u[i] , b = v[i] , c = w[i];
	    for(auto [d , count_d] : mp[a][b])
	    {
			if(c < d && d <= n && mp[a][c].count(d) && mp[b][c].count(d))
			{
				ans += mp[a][b][c] * mp[a][c][d] * mp[b][c][d];
//				cout << a << " " << b << " " << c << " "<<  d << endl;
			}
		}
	}
	cout << ans;
	return 0;
}
2024/8/28 15:15
加载中...