大佬们帮忙看看呗
查看原帖
大佬们帮忙看看呗
668320
fufuQAQ楼主2022/9/14 22:42

大佬们帮忙看看,dis的值为什么会改变

只查询,没更改任何操作,dis的值却变化了。这是为什么啊,大佬们求求了

测试异常结果
6
M 1 6
1 0 0 0 0 0
C 1
1
1 0 0 0 0 0
M 2 4
1 1 0 0 0 0
M 2 6
1 1 0 2 0 0
C 3
0
1 1 0 2 0 0   // 这里的值
C 2
3
1 3 0 2 0 0   //这里的值为什么跟上一行相比变了啊
cpp

//带权并查集 
#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int n;
int fa[N],dis[N],len[N];

int find(int x)//找x的根节点 
{
	if(x == fa[x])  return x;
	else
	{
		int t=fa[x];
		fa[x]=find(fa[x]);
		dis[x]+=dis[t];
	}
	return fa[x];
}

void merge(int x,int y)//错误点:关键还是合并这块,到底谁跟谁合并 
{
	int px=find(x);
	int py=find(y);
//	fa[x]=py;
//	dis[x]+=len[y];
//	len[y]+=len[x];

/*****************这里是为什么****************/ 
	fa[px]=py;
	dis[px]+=len[py];
	len[py]+=len[px];
/*****************这里是为什么****************/ 
}


int main()
{
	cin>>n;
	for(int i=1;i<=N;i++)
	{
		fa[i]=i;
		dis[i]=0;
		len[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		if(s=="M")
		{
			int b,c;
			cin>>b>>c;
			merge(b,c);
		}  
		if(s=="C")
		{
			int b;
			cin>>b;
			if(find(b)==b)    cout<<0<<endl;
			else   cout<<dis[b]<<endl;
		}
		for(int i=1;i<=6;i++)
		{
			cout<<dis[i]<<" ";
		}
		cout<<endl;
	} 
	return 0;
}
2022/9/14 22:42
加载中...