如何实现虫洞配对排列的无限循环检测？

我现在要实现一个问题：存在可沿x正方向行走时互相传送的虫洞点对，需要找出会导致**无限循环（来回传送）**的虫洞配对排列数量。

我的思路是先通过递归生成所有配对，再模拟每个点的路径，检测是否回到已访问过的点（标记visited[point] = true）。但实现时遇到了困难，因为需要同时处理当前虫洞连接的点和同一y坐标上的下一个点。

我用map存储配对关系，用set存储各y坐标对应的点集合，还写了check()函数来检测循环：

bool check() {
    for (int i = 0; i < n; i++) {
        int done = 1;
        pair<int, int> curp = wormholes[i];
        map<pair<int, int>, bool> visited;
        for (int j = 0; j < n; i++) visited[wormholes[j]] = false;
        visited[wormholes[i]] = true;
        while (done < n) {
            curp = pairs[curp];
            if (visited[curp]) return true;
            visited[curp] = true;
            if (xpery[curp.s].find(curp.f) == xpery[curp.s].end()) return false;

            done += 1;
            
            curp = mp(*(++(xpery[curp.s].find(curp.f))), curp.s);
            if (visited[curp]) return true;
            visited[curp] = true;

            done += 1;
        }
    }
    return false;
}

我用返回true表示陷入无限循环，false表示不会，但确定当前实现有问题，想知道有没有更优的实现方式？

1. 先修复现有check函数的明显bug #

你的check函数里有几个致命问题：

• 初始化visited的循环中，循环变量是j但用了i++，会导致死循环或数组越界，应改为j++
• 路径模拟逻辑混乱：done的累加和实际路径推进不匹配，且未处理走到y坐标最右端（无下一个点）的终止情况

2. 更高效的路径检测逻辑 #

不用遍历所有起点，只需检测每个连通分量是否存在环——只要有一个环就会触发无限循环：

• 对每个未访问的虫洞点，按以下步骤模拟路径：
  1. 当前点 → 传送点（通过配对映射）
  2. 传送点 → 同一y坐标上x更大的下一个点（如果存在）
  3. 重复步骤1-2，直到：
     • 走到已访问过的点：若该点属于当前路径，说明存在环，返回true
     • 走到y坐标最右端（无下一个点）：当前路径无环，标记所有途经点为已访问，继续处理下一个未访问点

3. 数据结构优化 #

• 不用map<pair<int,int>, bool>存储访问状态，把每个虫洞点映射为唯一整数索引（比如0~n-1），用vector<bool>存储访问状态，效率更高
• 对每个y坐标的点集合，提前按x排序并存入vector<vector<int>>（存储点的索引），找下一个点时用二分查找替代set的迭代器操作，速度更快

优化后的示例代码框架 #

// 预处理：将每个虫洞点映射到索引，wormholes为存储所有点的vector，point_to_idx为map<pair<int,int>, int>
// 每个y对应的点索引按x排序，存入y_to_points（vector<vector<int>>）

bool hasCycle() {
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        vector<int> path;
        int cur = i;
        while (true) {
            if (visited[cur]) {
                // 检查当前点是否在当前路径中
                auto it = find(path.begin(), path.end(), cur);
                if (it != path.end()) {
                    // 存在环
                    return true;
                }
                break;
            }
            visited[cur] = true;
            path.push_back(cur);
            // 第一步：传送
            auto [x, y] = wormholes[cur];
            int teleport = point_to_idx[pairs[{x, y}]]; // pairs为存储配对的map
            if (visited[teleport]) {
                auto it = find(path.begin(), path.end(), teleport);
                if (it != path.end()) return true;
                break;
            }
            visited[teleport] = true;
            path.push_back(teleport);
            // 第二步：找同一y的下一个点
            auto& points = y_to_points[y];
            // 二分查找teleport对应的x在points中的位置
            int pos = lower_bound(points.begin(), points.end(), teleport, [&](int idx, int target) {
                return wormholes[idx].first < wormholes[target].first;
            }) - points.begin();
            if (pos + 1 >= points.size()) {
                // 无下一个点，路径终止
                break;
            }
            cur = points[pos + 1];
        }
    }
    return false;
}

4. 递归生成配对的优化 #

用回溯法生成所有配对时，每次选一个未配对的点，仅和后面的点配对（避免重复计算如(0,1)和(1,0)这类相同配对），减少递归次数。

内容的提问来源于stack exchange，提问作者xq40