并查集 一种树形结构 有两种操作

1. 查询， 查一个元素在哪个集合

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

2. 合并， 将两个集合合并到一起

int union(int a, int b)
{
    a = find(a), b = find(b);

    if (a != b) p[b] = a;
}

并查集的经典应用

并查集判环可以找到成环的实际， 适用于无向图;

其他判环的应用

1. 拓扑排序只能判断一个点是否在环里，但不知道有几个二， 在哪个环;

2.SPFA可以判负环;

3. dfs可以找一个环上的节点;

4. tarjan算法可以找有向环；

5. 二分图判定可以找奇环;

2. 连通性问题

例题

CF217A

1. 两个点若 x1== x2 || y1 == y2, 合并

2. 两个不连通的点只需要+1个点必然连通

3. 答案就是连通块个数减一

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int p[N];
int x[N], y[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];

        p[i] = i;
    }

    // 直接暴力枚举 ... 没啥好说的
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (x[i] == x[j] || y[i] == y[j]) // 同横纵坐标
            {
                int a = find(i), b = find(j);

                if (a != b) p[b] = a;
            }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (p[i] == i) cnt++; // 最后判断连通块

    cout << cnt - 1; // 为什么要减一  比如3个点要连2条边才连通 就是这个道理


    return 0;
}

U125683

题目简述：给定一个矩阵， 每次给一个点向下火向右连边， 问什么时候形成环?

1.二位转一维 (x - 1) * n + y;

2. 若一条边的两个端点x和y已经在一棵树中， 那么再连边成环;

#include <bits/stdc++.h>
using namespace std;

const int N = 4e4 + 10;
int p[N];
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

int get(int x, int y)
{
    return (x - 1) * n + y;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n * n; i++) p[i] = i;

    char op;
    int x, y, cnt = 1; // cnt = 1 以防最后不会特判
    for (int i = 0; i < m; i++, cnt++)
    {
        cin >> x >> y >> op;

        int a = find(get(x, y)), b;

        if (op == 'D') b = find(get(x + 1, y));
        else b = find(get(x, y + 1)); // 好习惯写个转换函数

        if (a == b) break; // 连通成环结束

        p[b] = a;
    }

    if (cnt > m) cout << "draw";
    else cout << cnt;


    return 0;
}

P2661

1. 当点i转递给j时, find(j) == i, 即出现环;

2. 统计所有环的大小可以转换成统计递归的次数， 但不能路径压缩;

3. 再所有环的大小中取最小值即可;

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int p[N];
int cnt;

int find(int x)
{
    cnt++;

    if (p[x] != x) return find(p[x]);
    // 不能使用路径压缩会忽略大量情况
    // 也可以用那就要用带权并查集， 此题因为数据太水 而导致根本不需要带权并查集

    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) p[i] = i;

    int res = 1e9;
    for (int i = 1, t; i <= n; i++)
    {
        cin >> t;

        cnt = 0;

        if (i == find(t)) res = min(res, cnt); 
        else p[i] = t;
    }

    cout << res;


    return 0;
}

P2658

方法1： 暴力枚举D

1.在[0, 1e9]内枚举D值;

2.对于一个D值， 枚举矩阵的所有点， 并向下和右检查连边;

3. 若两个点的元素差的绝对值在枚举的D以内， 合并;

4. 最后检查所有”路标”是否根结点相同， 第一个D值即为答案

方法2 将D的枚举改为二分答案

时间复杂度(logD * N * M)

注意并查集要开n * m, 每次二分要初始化并查集

还有我们只要求路标连通

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int a[N][N];
int g[N * N], cnt;
int p[N * N];
int m, n;

int get(int x, int y)
{
    return (x - 1) * n + y;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

bool check(int d)
{
    for (int i = 1; i <= m * n; i++) p[i] = i;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i < m && abs(a[i][j] - a[i + 1][j]) <= d)
            {
                int a = get(i, j), b = get(i + 1, j);

                a = find(a), b = find(b);

                p[b] = a;
            }

            if (j < n && abs(a[i][j] - a[i][j + 1]) <= d)
            {
                int a = get(i, j), b = get(i, j + 1);

                a = find(a), b = find(b);

                p[b] = a;
            }
        }

    for (int i = 2; i <= cnt; i++)
        if (find(g[i - 1]) != find(g[i])) return false;

    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;

    int l = 0, r = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];

            r = max(r, a[i][j]);
        }

    for (int i = 1; i <= m; i++)
        for (int j = 1, v; j <= n; j++)
        {
            cin >> v;

            if (v == 1) g[++cnt] = get(i, j);
        }

    r++;

    while (l < r)
    {
        int mid = l + r >> 1;

        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r;


    return 0;
}