前言

距离 2026 CSP 还有 1 天。

并查集

并查集。

const int N = 20005;
int n, f[N], rank[N];

void init()
{
	for (int i = 1; i <= n; ++i)
	{
		f[i] = i;
		rank[i] = 1;
	}
}

int find(int u)
{
	if (f[u] == u) return u;
	return f[u] = find(f[u]);
}

void unq(int u, int v)
{
	u = find(u), v = find(v);
	if (rank[u] < rank[v]) swap(u, v);
	f[v] = u;
	if (rank[u] == rank[v]) ++rank[u];
}

最小生成树：$\text{Kruskal}$

树就是 $n$ 个点，$n-1$ 条边，且没有环的图。

所以在图中，选前 $n-1$ 小的边。但是要注意生成的时候不能有环。

判断环可以用并查集。连接一条边对应的两个点时，如果两个点是亲戚，那就跳过。一直到选到 $n-1$ 跳边或没有边。

这就是 Kruskal 算法。前提是图连通。

void kru()
{
	cnt = 0;
	ans = 0;
	sort(h + 1, h + m + 1, cmp);
	for (int i = 1; i <= m; ++i)
	{
		if (cnt == n - 1) break;
		int u = h[i].u, v = h[i].v, w = h[i].w;
		if (find(u) == find(v)) continue;
		
		++cnt;
		ans += w;
		unq(u, v);
	}
	if (cnt == n - 1) cout << ans;
	else cout << "orz";
}

最短路：$\text{Dijkstra}$

如果 $u\to v$ 边权为 $w$，那么可以通过 $dis_u+w$ 来松弛 $dis_v$。

Dijkstra 使用贪心思想。第一次计算 $u$ 的最短路一定是最短的。所以可以用一个 vis 判断有没有计算过 $u$。这样既可以加快，又可以保证正确。

void dij(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});

    while (q.size())
    {
        int u = q.top().second;
        q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for (auto nd : g[u])
        {
            int v = nd.first, w = nd.second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                q.push({-dis[v], v});
            }
        }
    }
}