[数据结构与算法]网络分析(并查集 + 差分)

2069. 网络分析

网络分析

题意：动态维护集合的合并和集合内元素的查询 思路：
1.类似区间合并单点查询，可以构造子节点和父节点直接的差分，即子节点真实值为该节点的值加上父节点的值,。
2.由于并查集的路径压缩,每一次路径压缩都需要加上当前父节点的值

例如如图
1.当将集合4合并到集合1之下时候，为满足差分保证5,6不变,$w[4]?=w[1]$.
2.当将5-4-1的路径压缩程5-1时,$w[5]+=w[4]$

样例输入：

4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

样例输出：

13 13 5 3

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e4 + 10;
int p[N], w[N], cnt[N];
int n, m;

int find(int x)
{
    if(x != p[x])
    {
        int t = find(p[x]);
        if(p[x] != t) w[x] += w[p[x]];
        return p[x] = t;
    }
    
    return p[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    for(int i = 1; i <= m; i ++ )
    {
        int a, b, op;
        scanf("%d%d%d", &op, &a, &b);
        if(op == 1 && a == b) continue;
        if(op == 1)
        {
            a = find(a), b = find(b);
            if(a != b)
            {
                p[b] = a;
                w[b] -= w[a];
            }
        }
        else
        {
            int pa = find(a);
            w[pa] += b;
        }
    }
    for(int i = 1; i <= n; i ++ )
    {
        if(find(i) == i) cout << w[i] << " ";
        else cout << w[i] + w[p[i]] << " ";
    }
    
    return 0;
}

?