【夯实算法基础】并查集

文章目录

- - AcWing 1250. 格子游戏
  - AcWing 1252. 搭配购买
  - AcWing 237. 程序自动分析
  - AcWing 238. 银河英雄传说
  - AcWing 239. 奇偶游戏
  - AcWing 240. 食物链

AcWing 1250. 格子游戏

⛵️ 思路

什么时候会围成一个封闭的圈呢，可以这样想：如果我们要连的那一条边已经连起来了，那么我在连一次不就成了一个圈了吗。可以使用并查集将连起来的点都整合到一个集合当中去，这样就可以很快的查询两个点是不是同属于一个集合了。

代码

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int p[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
// 这种hash操作只适用于行和列相等的情况
// 如果行和列不等，可以使用给每个点设置一个标记
int get(int x, int y)
{
    return x * n + y;
}
void solve()
{
    cin >> n >> m;
    // 最多有 n * n + n 个
    for (int i = 1; i <= n * n + n; i++)
        p[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        char c;
        cin >> x >> y >> c;
        int a = get(x, y);
        if (c == 'D')
            x++;
        else
            y++;
        int b = get(x, y);
        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            cout << i;
            return;
        }
        else
            p[pa] = pb;
    }
    cout << "draw";
    return;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

AcWing 1252. 搭配购买

**思路 ** ：并查集+01背包

将捆绑销售的一些物品整合成一个物品，这一步用并查集来实现每个物品的价钱和价值总和。

现在问题就变成了有w块钱可以选择买一些物品并实现价值最大，很容易就想到了01背包。(关于背包问题可以参考我的这篇博客：背包问题)

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m, V;
int v[N]; // 价钱
int w[N]; // 价值
int f[N]; //花i钱能买到花的最大价值
int p[N]; //并查集数组
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void solve()
{
    cin >> n >> m >> V;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
        p[i] = i;
    }
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a != b)
        {
            p[a] = b;
            v[b] += v[a];
            w[b] += w[a];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (p[i] != i)
            continue;
        for (int j = V; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    cout << f[V];
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

AcWing 237. 程序自动分析

 思路

先考虑所有相等的条件，如果两个元素相等，那么就将它俩放到同一个集合中去，在考虑所有不等的条件，如果两个元素在同一个集合中，说明它俩之前是相等的，这样就产生了矛盾。

这题数据范围比较大，所以我们需要对元素进行离散化，离散化方式有两种：

保序：排序+判重+二分
不保序：map / hash

**代码1（保序） **

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int p[N];
vector v1, v2;
vector v;
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void merage(int a, int b)
{
    p[find(a)] = find(b);
}
int get(int x)
{
    return lower_bound(all(v), x) - v.begin() + 1;
}
void solve()
{
    v1.clear();
    v2.clear();
    v.clear();
    cin >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v.pb(a);
        v.pb(b);
        if (c == 1)
            v1.pb({a, b});
        else
            v2.pb({a, b});
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    int n = v.size();
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 0; i < v1.size(); i++)
    {
        int a = get(v1[i].x);
        int b = get(v1[i].y);
        merage(a, b);
    }
    bool ok = true;
    for (int i = 0; i < v2.size(); i++)
    {
        int a = get(v2[i].x);
        int b = get(v2[i].y);
        if (find(a) == find(b))
        {
            ok = false;
            break;
        }
    }
    if (ok)
        YES;
    else
        NO;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

 代码2（不保序）

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e5 + 10;
unordered_map f;
int find(int x)
{
    if (f[x] != x)
        f[x] = find(f[x]);
    return f[x];
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        f.clear();
        int n;
        cin >> n;
        vector v;
        int k = 1;
        while (n--)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (f.count(a) == 0)
            {
                f[a] = a;
            }
            if (f.count(b) == 0)
            {
                f[b] = b;
            }
            int l = find(a);
            int r = find(b);
            if (c == 1)
            {
                f[l] = r;
            }
            else
            {
                v.push_back({l, r});
            }
        }
        for (int i = 0; i < v.size(); i++)
        {
            int l = v[i].x;
            int r = v[i].y;
            l = find(l);
            r = find(r);
            if (l == r)
            {
                k = 0;
                break;
            }
        }

        if (k)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

AcWing 238. 银河英雄传说

 思路

并查集可以用于维护具有传递性关系的作用，每个集合的大小，绑定到根节点上，每个点到根节点的距离，绑定到每个元素的节点上。

我们直接用并查集就可以查询两个点是不是在一个队列中，但是要记录每个点之间的距离就不好求了。求两个点之间的距离我们可以用到前缀和的思想。

d[x] 表示每个点到根节点的距离

size[x]表示每个集合的节点个数

p[x]表示每个点的祖先节点是谁

我们从一般出发，先来看合并两个点的情况：

接下来我们再看合并两个集合大小为2的集合的情况：

通过这两个例子我们可以发现一些性质，当我们要合并a,b两个集合时

需要三步：

d[p[a]] = size[p[b]] ：a的根节点到b的根节点的距离更新
size[p[b]] += size[p[a]] ：合并后每个集合的大小要更新
p[p[a]] = p[p[b]] ：更新祖先节点，每一次合并都要更新

求每个点到根节点的距离时在路径压缩中完成的，也需三步：

root = find(p[x])：比如上图中的3号点的根节点1号点
d[x] += d[p[x]]：一个点到它的根节点的距离加上它的根节点到根节点的根节点的距离。比如上图中的4号点
p[x] = root , 更新祖先节点

 代码

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 3e4 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int p[N], s[N], d[N]; // d是每个点到p[x]的距离
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}
void solve()
{
    cin >> m;
    for (int i = 1; i < N; i++)
    {
        p[i] = i;
        s[i] = 1;
    }
    while (m--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        int pa = find(a), pb = find(b);
        if (op[0] == 'M' && pa != pb)
        {
            d[pa] = s[pb];
            s[pb] += s[pa];
            p[pa] = pb;
        }
        if (op[0] == 'C')
        {
            if (pa != pb)
                cout << -1 << endl;
            else
                cout << max(0, abs(d[a] - d[b]) - 1) << endl;
        }
    }
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

AcWing 239. 奇偶游戏

 思路1：边带权

 代码

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N / 2, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int p[N];
int d[N]; // 0 代表相同，1代表不同
unordered_map ma;
int get(int x)
{
    if (ma.count(x) == 0)
        ma[x] = ++n;
    return ma[x];
}
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}
void solve()
{
    cin >> n >> m;
    n = 0;
    for (int i = 1; i < N; i++)
        p[i] = i;
    int ans = m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        string s;
        cin >> a >> b >> s;
        a = get(a - 1);
        b = get(b);
        int pa = find(a), pb = find(b);
        int t = 0;
        if (s == "odd")
            t = 1;
        if (pa == pb)
        {
            if (d[a] ^ d[b] != t)
            {
                ans = i - 1;
                break;
            }
        }
        else
        {
            p[pa] = pb;
            d[pa] = t ^ d[a] ^ d[b];
        }
    }
    cout << ans;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

 思路2：扩展域

 代码2

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N / 2, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int p[N];
unordered_map ma;
int get(int x)
{
    if (ma.count(x) == 0)
        ma[x] = ++n;
    return ma[x];
}
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void solve()
{
    cin >> n >> m;
    n = 0;
    for (int i = 1; i < N; i++)
        p[i] = i;
    int ans = m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        string s;
        cin >> a >> b >> s;
        a = get(a - 1);
        b = get(b);
        if (s == "even")
        {
            if (find(a) == find(b + M))
            {
                ans = i - 1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + M)] = find(b + M);
        }
        else
        {
            if (find(a) == find(b))
            {
                ans = i - 1;
                break;
            }
            p[find(a)] = find(b + M);
            p[find(b)] = find(a + M);
        }
    }
    cout << ans;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

AcWing 240. 食物链

 思路：边带权

d[x] 表示x到它父亲的距离，以来表示几个点之间的关系

d[x] % 3 == 0,表示它和父节点是同类

d[x] % 3 == 1表示它和可以吃父节点

d[x] % 3 == 2表示可以被父节点吃

这样我们就可以用点到父节点的距离来表示关系，所有的距离都以根节点为基础。

如果x和y是同类关系，但此时不在同一个集合中，那么

p[find(a)] = find(b)
(d[x] + d[p[x]]) % 3 == d[y] % 3

由于p[x]的父节点发生了变化，那么它到父节点的距离也要变化:

d[p[x]] = (d[y] - d[x]) % 3

如果x吃y，而且它俩不在同一个集合中，那么

p[find(a)] = find(b)
(d[x] + d[p[x]]) % 3 == (d[y] + 1) % 3

d[p[x]] = (d[y] - d[x] + 1) % 3

我们要在find函数中既要更新父节点是谁，还要更新d[x]

我们知道d[x]等于它到父节点的距离，此时父节点已经发生了变化，那么d[x]就等于它到父节点的距离加上父节点到它的父节点的距离，然后在更新x的父节点（此时已经是根结点）了。

引用文章：(AcWing 240. 食物链—数组d的真正含义以及find()函数调用过程)[https://www.acwing.com/solution/content/15938/]

 代码

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
typedef priority_queue, less> Q;
#define x first
#define y second
#define endl 'n'
#define ppb pop_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int p[N];
int n, m;
int d[N];
int ans;
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        cin >> op >> x >> y;
        // 假话
        if (x > n || y > n)
        {
            ans++;
            continue;
        }
        if (op == 1)
        {
            int pa = find(x), pb = find(y);
            if (pa == pb)
            {
                // 如果它俩相差求余3结果不同，表示不是同类关系
                if ((d[x] - d[y] + 3) % 3)
                {
                    ans++;
                    continue;
                }
            }
            else
            {
                p[pa] = pb;
                d[pa] = (d[y] - d[x] + 3) % 3;
            }
        }
        else
        {
            if (x == y)
            {
                ans++;
                continue;
            }
            int pa = find(x), pb = find(y);
            if (pa == pb)
            {
                // 如果它俩求余结果不是差1的关系，表示不是x吃y的关系
                if ((d[x] - d[y] - 1) % 3)
                {
                    ans++;
                    continue;
                }
            }
            else
            {
                p[pa] = pb;
                d[pa] = (d[y] - d[x] + 1) % 3;
            }
        }
    }
    cout << ans;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}

刚开始学基础课的时候这点怎么也不能理解，后来在学的时候觉得醍醐灌顶，内心想当时为啥学不会呢，这就是一个学习的过程吧。

【夯实算法基础】 并查集

Java相关栏目本月热门文章

【夯实算法基础】并查集