社区讨论
建议更新一下数据
P1892[BalticOI 2003] 团伙参与者 1已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi7cn2jg
- 此快照首次捕获于
- 2025/11/20 19:29 4 个月前
- 此快照最后确认于
- 2025/11/20 19:29 4 个月前
RT,
众所周知,这道题有一个十分优秀的解法——建立补集。
关押罪犯和食物链都可以使用这种方法。但不同的是,这道题要求统计团伙的个数,也就是统计所有包含了正点的集合个数,像这样。
CPP for(int i=1;i<=n;i++) vis[find(i)]=1;
for(int i=1;i<=n*2;i++) ans+=vis[i];
但是在写代码的过程中,突然发现,写成这样
CPPfor(int i=1;i<=n;i++)
ans+=(find(i)==i);
竟然也过了样例,然后闲的没事交了一遍,发现它竟然神奇的AC了。但是这种方法是显然不对的。因为合并是任意的,无法保证所有包含正点的集合的根都在正点上。
但由于这道题给的数据凑巧的符合了我
大家平时写的合并顺序,所以就十分凑巧的AC了,如果交换合并顺序的话,甚至过不了样例。
讨论区也有一些讨论提及到了关于合并顺序的问题,我想也应该是这个原因。故希望管理大人能修改一下道题的数据,以免对并查集造成什么误解。修改这道题的数据也不是十分困难,只要把一部分数据点的x和y交换一下,就可以使大部分同学发现这个问题所在。
回复
共 2 条回复,欢迎继续交流。
正在加载回复...