问题描述 你现在是城市的主人 现在有 n 个村庄要修建 m 条路每修建一条路道路是双向的输出至少还需要修建几条可以让所有村庄互相可达。 一开始路为 0 条 数据保证有解 输入格式 第一行两个整数 nm 0≤nm≤10 5 接下来有 m 行每行 ab 代表修建了一条从第 a 个村庄到第 b 个村庄的路。 1≤ab≤n a 和 b 可能相同。 输出格式 一共 m 行第 i 个数代表已经修
思路：使用并查集，每次修建一条路时，判断两个村庄是否已经在同一个集合中，如果不在，则将它们合并，同时需要记录当前集合的数量，对于每次修建路的操作，输出当前集合数量-1即可。
时间复杂度：每次修建路需要进行一次并查集查找和合并操作，时间复杂度为O(logn)，总时间复杂度为O(mlogn)。
C++代码：
原文地址: http://www.cveoy.top/t/topic/bBJl 著作权归作者所有。请勿转载和采集!