不会写,走了
by wkz2010 @ 2023-10-02 11:12:42
@[wkz2010](/user/981741) 你不会写来凑什么热闹,[老师发的比赛](https://www.luogu.com.cn/contest/136215)赶紧去做,题目在群里
by yinbe @ 2023-10-02 11:22:30
```cpp
#include<iostream>
using namespace std;
int T,fa[30005],fa_front[30005],fa_cnt[30005];
int find_fa(int i)
{
if(fa[i]==i)
{
return i;
}
int root=find_fa(fa[i]);
fa_front[i]+=fa_front[fa[i]];
return fa[i]=root;
}
int main()
{
for(int i=1;i<=30000;i++)
{
fa[i]=i;
fa_cnt[i]=1;
}
scanf("%d",&T);
while(T--)
{
char c;
int i,j;
cin>>c;
scanf("%d%d",&i,&j);
if(c=='C')
{
if(find_fa(i)!=find_fa(j))
{
printf("-1\n");
}
else
{
printf("%d\n",abs(fa_front[i]-fa_front[j])-1);
}
}
if(c=='M')
{
int x=find_fa(i),y=find_fa(j);
fa[x]=y;
fa_front[x]=fa_cnt[y];
fa_cnt[y]+=fa_cnt[x];
}
}
return 0;
}
```
改成这样就可以了
by 317_sky @ 2023-10-03 15:53:10
合并的时候使用find_fa会导致,fa_front被错误的更新。而且在find_fa的时候,先更新再递归会导致父节点的值还没被更新,子节点就已经更新完了,所以要先递归在更新子节点
by 317_sky @ 2023-10-03 16:06:17
@[317_sky](/user/457587) 感谢,已AC
by yinbe @ 2023-10-09 21:58:15
@[wkz2010](/user/981741) 所以,你会了吗?
by yinbe @ 2023-10-09 21:58:58