跳蚤国王和蛐蛐国王的游戏：并查集求解最小替换次数

"这是一个图论的问题，可以使用并查集来解决。\n\n首先，我们需要将网格中的每个格子编号。将第 i 行第 j 列的格子编号为 (i-1) * m + j。这样，网格中的 n 行 m 列的格子就被编号为 1,2,…,n×m。\n\n然后，我们需要定义并查集的操作。首先，我们需要定义一个数组 fa，大小为 n×m+1，并初始化为 [0,1,2,…,n×m]。\n\n接下来，我们需要定义两个操作：\n\n1. find(x)：返回节点 x 的根节点。\n\n2. merge(x, y)：将节点 x 和节点 y 所在的集合合并。\n\n在这个问题中，我们需要进行如下操作：\n\n1. 遍历所有的蛐蛐格子，将其合并为一个集合。\n\n2. 统计所有的跳蚤格子的个数 cnt。\n\n3. 遍历所有的跳蚤格子，如果其相邻的格子不在同一个集合中，则将其合并为一个集合，并将 cnt 减一。\n\n4. 判断 cnt 是否大于等于 2。如果是，则输出 cnt 的值；否则，输出 -1。\n\n下面是具体的实现步骤：\n\n1. 定义一个函数 getRoot，用于返回节点 x 的根节点。\n\n2. 定义一个函数 merge，用于将节点 x 和节点 y 所在的集合合并。\n\n3. 定义一个函数 solve，用于解决每组数据。\n\n - 首先，遍历所有的蛐蛐格子，将其合并为一个集合。\n - 然后，统计所有的跳蚤格子的个数 cnt。\n - 接下来，遍历所有的跳蚤格子，如果其相邻的格子不在同一个集合中，则将其合并为一个集合，并将 cnt 减一。\n - 最后，判断 cnt 是否大于等于 2。如果是，则输出 cnt 的值；否则，输出 -1。\n\n4. 读入数据，并依次调用 solve 函数来解决每组数据。\n\n下面是具体的代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nconst int MAXN = 1000005;\nint fa[MAXN];\n\nint getRoot(int x) {\n if (fa[x] == x) return x;\n return fa[x] = getRoot(fa[x]);\n}\n\nvoid merge(int x, int y) {\n int rootX = getRoot(x);\n int rootY = getRoot(y);\n if (rootX != rootY) fa[rootX] = rootY;\n}\n\nvoid solve(int n, int m, int c) {\n for (int i = 1; i <= n * m; i++) {\n fa[i] = i;\n }\n \n for (int i = 1; i <= c; i++) {\n int x, y;\n cin >> x >> y;\n merge(x, y);\n }\n \n int cnt = n * m - c;\n vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n \n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (i == 1 || i == n || j == 1 || j == m) {\n int root = getRoot((i - 1) * m + j);\n for (auto dir : dirs) {\n int nx = i + dir[0];\n int ny = j + dir[1];\n if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {\n int nroot = getRoot((nx - 1) * m + ny);\n if (root != nroot) {\n merge(root, nroot);\n cnt--;\n }\n }\n }\n }\n }\n }\n \n if (cnt >= 2) {\n cout << cnt << endl;\n } else {\n cout << -1 << endl;\n }\n}\n\nint main() {\n int T;\n cin >> T;\n \n while (T--) {\n int n, m, c;\n cin >> n >> m >> c;\n solve(n, m, c);\n }\n \n return 0;\n}\n\n\n该算法的时间复杂度为 O(nm)。