AcWing 2069. 网络分析【并查集/树上差分】

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2069. 网络分析【并查集/树上差分】原题链接简单

作者：

滑稽_ωﾉ , 2020-07-08 17:23:14 , 所有人可见 , 阅读 7942

104

27

题目描述

给出一个 $n$ 个孤立点的图，每个点上的权值都是 $0$ ，进行 $m$ 次操作
操作 $1$ ：把两个点所在的连通块合并起来
操作 $2$ ：向某个点所在的连通块的所有点累加一个值
$n \leq 10^4, m \leq 10^5$

最后输出每个点上的权值

并查集树上差分

我们通过并查集合并连通块，保证同一个连通块内的点同属一个集合
对于每一个合并操作，找到两个点所属的集合
如果这两个点不在同一连通块，那么我们构造一个新点，使这个新点成为集合合并后的根节点

这样进行 $k$ 次有效合并操作后，就会产生 $k$ 个新点
我们所构造的图是若干棵树，编号为 $1-n$ 的节点都是树的叶子节点

对于每次连通块累加操作，我们只需要向集合的根节点累加一个值即可
最后对我们所构造出来的一堆树DP（只是遍历一下），把每个点的权值下放到子树中的所有节点中
然后依次输出编号为 $1-n$ 的节点的权值即可

时间复杂度 $O(n + m)$

C++ 代码

#include<cstdio>
#include<cstring>

const int N = 200010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int f[N];

void dfs(int u, int fa)
{
    f[u] += f[fa];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j, u);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n * 2; i ++)  p[i] = i;

    int root = n + 1;
    while(m --)
    {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        if(op == 1)
        {
            a = find(a), b = find(b);
            if(a != b)
            {
                p[a] = p[b] = root;
                add(root, a);
                add(root, b);
                root ++;
            }
        }
        else
        {
            a = find(a);
            f[a] += b;
        }
    }

    for(int i = n + 1; i < root; i ++)
        if(p[i] == i)  dfs(i, 0);

    for(int i = 1; i <= n; i ++)
        printf("%d ", f[i]);
    return 0;
}

58 评论

Cauchy 2023-03-27 16:29

优雅不过如此！

Wind_59 2024-03-20 11:45

java版本如下：

//package p1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
     static int n,m,idx;
     static final int N=20010;
     static int[] h=new int[N];
     static int[] ne=new int[N];
     static int[] e=new int[N];
     static int[] p=new int[N];
     static int[] f=new int[N];

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

     static void add(int a,int b) {
         e[idx]=b;
         ne[idx]=h[a];
         h[a]=idx++;
     }

     static void dfs(int u,int fa) {
         f[u]+=f[fa];
         for(int i = h[u]; i!=-1; i = ne[i])
            {
                int j = e[i];
                dfs(j, u);
            }
     }

     public static void main(String[] args) throws IOException {

        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        String[] s=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);

        for(int i = 1; i <= n * 2; i ++)  p[i] = i;
        Arrays.fill(h,-1);

        int root=n+1;

        while(m-->0) {
            int op,a,b;
            s=br.readLine().split(" ");
            op=Integer.parseInt(s[0]);
            a=Integer.parseInt(s[1]);
            b=Integer.parseInt(s[2]);

            if(op==1) {
                a=find(a);
                b=find(b);
                if(a!=b) {
                    p[a]=p[b]=root;
                    add(root,a);
                    add(root,b);
                    root++;
                }
            }else {
                a=find(a);
                f[a]+=b;
            }


        }
        for(int i = n + 1; i < root; i ++)
            if(p[i] == i)  dfs(i, 0);
        for(int i=1;i<=n;i++) {
            System.out.print(f[i]+" ");
        }
    }

}

芩渊 2024-03-21 19:05

佬咱数组定义能写下注释不代码写得很漂亮有注释就更好了wuwuwu

巴拉巴拉巴拉 2024-03-25 15:17

真的是太贴心了，先不管看不看的懂，我直接点赞

delicate_1 11个月前

给大佬跪了orz

h闵 7个月前

不理解的话可以看我下面的补充，这样就可以很好的理解了，非高手可以看看。

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;
int p[N],d[N];
//这个p[x]的意思就是x这个节点的父节点的。
//这个d[x]的意思就是给x这个节点上发送一条大小为d[t]的信息的。这个还只是一个根据输入某些节点发送的信息的，还并不是最后要输出的答案的。

//下面这个函数的作用就是找到x这个节点的根节点的。以及加上下面的功能的。
//下面这个函数还有一个功能，就是把x这个点的权值变为了x到根节点这条路径上（不包括根节点r）所有点的权值之和。这样答案要求x这个点的真实值的时候就是等于d[x] + d[r]的。
int find(int x)
{
    if(p[x] == x || p[p[x]] == p[x]) return p[x];  //这一行的意思就是如果当前点就是根节点或者是当前点的父节点是根节点的意思的。 
    int r = find(p[x]);
    d[x] += d[p[x]];
    p[x] = r;
    return r;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) p[i] = i;
    while(m--)
    {
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t == 1)  //这个就是把两个点连接起来的意思。 
        //对于下面的这个我有疑惑，因为就是d[a] -= d[b]了的，原则上只有a这一个点进行了减去d[b]的，但是经过我的验证a这个点为根的子树中所有点其实权值都剪去了d[b]的。
        //而这个需要进行一次find()才可以达到目的，也就是说，正好是输出的时候达到了这个目的。
        {
            a = find(a),b = find(b);
            if(a != b)
            {
                d[a] -= d[b];
                p[a] = b;  //a,b这两个节点对应的本来是两棵树的，这一行之后就是一棵树了的，而且a这棵树就是b这棵树的儿子了的。
            }
        }
        else  //由于任意点x的真实值等于d[x] + d[find(x)]，当为2的时候给根节点加上b，所以每个点的真实值就都是加上了b了的，这个可以达到。??理解了。
        {
            a = find(a);
            d[a] += b;
        }
    }

    for(int i = 1;i <= n;i++)
    {
        if(i == find(i)) printf("%d ",d[i]);  //这个就是根节点的情况的。 
//      if(i == find(i)) printf("%d\n",d[i]);  //这个就是根节点的情况的。上面一行才是可以通过的，这一行是在理解这个程序的。 
        else 
        {
            printf("%d ",d[i] + d[find(i)]);  //这一行才是可以通过的，下面都是在理解这个程序的。

            //经过我的验证，下面的find()函数是先执行才会进行得到d[i] + d[find(i)]的，不然的话下面输出的两个d[i]就是会不一样的。但是显然下面输出的是一样的。
            //所以，下面的这个find()函数确实是做到了当连接边的时候的只进行一个点进行减去，但是这棵子树的所有点的权值都减去了。上面的疑惑就解决了的。
          //  printf("%d ",d[i]);
          //  printf("%d ",d[i] + d[find(i)]);
          //  printf("%d\n",d[i]);
        }
    }

    return 0;
}