无向图循环检测：深度优先搜索与并查集应用详解

import java.util.*;

class GraphDFS {
    private Map<String, List<String>> adj; // 邻接列表表示图
    private Set<String> visited;         // 记录已访问的节点
    private Map<String, String> parent;  // 记录节点的父节点

    public GraphDFS(Map<String, List<String>> adjacencyList) {
        this.adj = adjacencyList;
    }

    /**
     * 检测无向图中是否存在循环。
     * @return 如果存在循环返回 true，否则返回 false。
     */
    public boolean hasCycle() {
        visited = new HashSet<>();
        parent = new HashMap<>();

        // 遍历所有节点，确保处理非连通图中的所有组件
        // 收集所有可能的节点，包括那些没有邻居的节点
        Set<String> allNodes = new HashSet<>(adj.keySet());
        for (List<String> neighbors : adj.values()) {
            allNodes.addAll(neighbors);
        }

        for (String node : allNodes) {
            if (!visited.contains(node)) {
                // 从未访问的节点开始DFS，父节点设为null
                if (dfs(node, null)) {
                    return true; // 发现循环
                }
            }
        }
        return false; // 没有发现循环
    }

    /**
     * 深度优先搜索辅助函数。
     * @param u 当前访问的节点
     * @param p u的父节点
     * @return 如果在当前DFS路径中发现循环返回 true，否则返回 false。
     */
    private boolean dfs(String u, String p) {
        visited.add(u); // 标记当前节点为已访问
        parent.put(u, p); // 记录父节点

        // 遍历当前节点的所有邻接点
        for (String v : adj.getOrDefault(u, Collections.emptyList())) {
            if (!visited.contains(v)) {
                // 如果邻接点v未被访问，则递归地进行DFS
                if (dfs(v, u)) {
                    return true; // 递归调用发现循环
                }
            } else if (!v.equals(p)) {
                // 如果邻接点v已被访问，且v不是u的父节点，则发现回边，存在循环
                return true;
            }
        }
        return false; // 当前路径中未发现循环
    }
}

import java.util.*;

class UnionFind {
    private Map<String, String> parent; // 存储每个元素的父节点
    private Map<String, Integer> rank;   // 存储每个集合的秩（用于按秩合并优化）

    public UnionFind(Set<String> nodes) {
        parent = new HashMap<>();
        rank = new HashMap<>();
        for (String node : nodes) {
            parent.put(node, node); // 初始时每个节点的父节点是自己
            rank.put(node, 0);      // 初始秩为0
        }
    }

    /**
     * 查找元素i的代表元素（根节点），并进行路径压缩。
     * @param i 要查找的元素
     * @return 元素i的代表元素
     */
    public String find(String i) {
        if (!parent.containsKey(i)) {
            // 如果节点不在并查集中，可以根据需求处理，例如抛出异常或返回自身
            parent.put(i, i);
            rank.put(i, 0);
            return i;
        }
        if (parent.get(i).equals(i)) {
            return i;
        }
        String root = find(parent.get(i)); // 递归查找根
        parent.put(i, root); // 路径压缩
        return root;
    }

    /**
     * 合并元素i和j所在的集合。
     * @param i 元素i
     * @param j 元素j
     * @return 如果成功合并（未形成循环）返回 true，否则返回 false（已在同一集合，形成循环）。
     */
    public boolean union(String i, String j) {
        String rootI = find(i);
        String rootJ = find(j);

        if (!rootI.equals(rootJ)) { // 如果不在同一个集合
            // 按秩合并优化：将秩较小的树连接到秩较大的树的根上
            if (rank.get(rootI) < rank.get(rootJ)) {
                parent.put(rootI, rootJ);
            } else if (rank.get(rootI) > rank.get(rootJ)) {
                parent.put(rootJ, rootI);
            } else { // 秩相等时，任意连接，并将新根的秩加1
                parent.put(rootJ, rootI);
                rank.put(rootI, rank.get(rootI) + 1);
            }
            return true; // 合并成功，未形成循环
        }
        return false; // 已经在同一个集合，添加这条边会形成循环
    }
}

class GraphUnionFind {
    private Map<String, List<String>> adj; // 邻接列表表示图

    public GraphUnionFind(Map<String, List<String>> adjacencyList) {
        this.adj = adjacencyList;
    }

    /**
     * 检测无向图中是否存在循环。
     * @return 如果存在循环返回 true，否则返回 false。
     */
    public boolean hasCycle() {
        // 收集所有节点，包括那些没有邻居的节点
        Set<String> allNodes = new HashSet<>(adj.keySet());
        for (List<String> neighbors : adj.values()) {
            allNodes.addAll(neighbors);
        }

        UnionFind uf = new UnionFind(allNodes);

        // 遍历所有边。对于无向图，每条边 (u,v) 会在邻接列表中出现两次
        // 我们需要确保每条边只被处理一次，以避免重复判断或错误判断
        Set<String> processedEdges = new HashSet<>(); // 用于记录已处理的边对，例如 "a-b"
        for (String u : adj.keySet()) {
            for (String v : adj.getOrDefault(u, Collections.emptyList())) {
                // 确保只处理一次边 (u,v)，例如通过规范化边表示或跳过已处理的逆向边
                String edge