求助分析时间复杂度
  • 板块灌水区
  • 楼主Zhang_Wenjie
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/6/6 09:43
  • 上次更新2024/6/6 16:10:40
查看原帖
求助分析时间复杂度
481621
Zhang_Wenjie楼主2024/6/6 09:43

这里边感觉变量会相互影响,怎么分析呢?

代码实际上实现的是在无自环、重边的带权无向图,用并查集求边联通块

#include <bits/stdc++.h>
#define re register int 
using namespace std;
typedef pair<int, int> PII;
const int N = 2e6 + 10, M = 2e6 + 10;
const int C = 1e6; 
 
struct edge
{
	int to, w, next;
}e[M];
int top, h[N], dist[N], fa[N];
int n, m;
bool vis[N];
 
vector<PII> g[N];
vector<int> t;
 
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
 
inline void add(int x, int y, int w)
{
	e[++ top] = (edge){y, w, h[x]};
	h[x] = top;
}
 
inline void build()
{
	for (re c = 1; c <= C; c ++)
	{
		if (g[c].empty()) continue;
 
		t.clear();
		for (auto x : g[c]) 
			t.push_back(x.u), t.push_back(x.v);
 
		sort(t.begin(), t.end());
		t.erase(unique(t.begin(), t.end()), t.end());
 
		for (auto i : t) fa[i] = i;
 
		for (auto x : g[c])
		{
			if (find(x.u) != find(x.v)) fa[find(x.u)] = find(x.v);
		}
 
		for (auto i : t)
		{
			int res = find(i);
 
			...
 
		}
 
	}
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> m;
	for (re i = 1; i <= m; i ++)
	{
		int x, y, c; cin >> x >> y >> c;
		g[c].push_back({x, y});
	}
	build();
 
	return 0;
}
2024/6/6 09:43
加载中...