acwing2069. 网络分析

题目

小明正在做一个网络实验。

他设置了 n 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。

两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。

所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

##题解

#include<iostream>
using namespace std;
const int N=10010;
int p[N];
int d[N];
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 p[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--){
        int c,a,b;
        cin>>c>>a>>b;
        if(c==1){
            a=find(a);
            b=find(b);
            //a指向b
            if(a!=b){
                d[a]-=d[b];
                p[a]=b;
            }
        }else{
            a=find(a);
            d[a]+=b;
        }
    }
    for(int i=1;i<=n;i++){
        if(i==find(i))cout<<d[i]<<" ";
        else cout<<d[i]+d[find(i)]<<" ";
    }
    
    return 0;
}