边的数量很多时如何来预处理而导致原来的稠密图变为稀疏图从而躲过RE或TLE的方法

https://www.jisuanke.com/course/2459/257590
我开始建了所有边,就变成了n2条边,如果n是20万,这个图不可能存下来导致RE。
实际上,可以先做一遍并查集,确立所有的a[i]+a[j]型边,然后再做m条边的最小生成树。
当遇到边的数量非常多时,可以先用并查集去掉多余的边。

上一篇:SGU507. Treediff 题解 树上启发式合并 $O(n \log^2 n)$ 解法(TLE)


下一篇:2019.07.11【NOIP提高组】模拟 A 组 总结