AcWing2069.网格分析

【题目链接】2069. 网络分析 - AcWing题库

输入样例1：

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

输出样例1：

13 13 5 3

【代码及详细注释】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,p[N],d[N];
//p数组用于维护并查集，d数组用于维护大小 
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()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) p[i]=i;//初始化并查集
	while(m--)
	{
		int t,a,b;
		cin>>t>>a>>b;
		if(t==1)//执行合并操作
		{
			a=find(a),b=find(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)];//如果不是根节点需要输出这条路径上所有的距离和 
		cout<<" ";
	}
	return 0;
}