这里边感觉变量会相互影响,怎么分析呢?
代码实际上实现的是在无自环、重边的带权无向图,用并查集求边联通块
#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;
}