力扣解题思路：并查集

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3

如果移除一条边可以成为一棵树那就意味着这个图存在环路，那么移除这个环的任意边即可（题目要求是最后一条边），所以我们可以使用并查集来记录每个节点的最前前驱节点，也就是父节点，如果两个节点的父节点相同，证明这两个节点是相连的，如果这两个节点不相连，我们可以将其父节点改成相同来使这两个节点连同。现在我们来定义并查集的数据结构：

class DSU{
    int[] parent;
    public DSU(int N){
        parent = new int[N+1];
        for(int i=0;i<N;i++){
            parent[i] = i;
        }
    }
    public int find(int x){
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x,int y){
        parent[find(x)] = find(y);
    }
}

然后创建一个DSU对象进行上述操作，在本题中，我们只要遇到两个不相连的节点，如果遍历到他们的边，则将其联通，如果本身就联通又遍历到他们的边，那证明存在环，移除即可。

public int[] findRedundantConnection(int[][] edges) {
    int N = edges.length;
    DSU dsu = new DSU(N);
    int[] res = new int[]{-1,-1};
    for (int[] e : edges) {
        int u = e[0], v = e[1];
        if (dsu.find(u) == dsu.find(v)) {
            res[0] = u;
            res[1] = v;
        }
        dsu.union(u, v);
    }
    return res;
}

思路：

这一题需要注意的两个点是题目所给的都是字符串数组，需要自己分割出数据，用indexOf方法会比较方便，另外两个相邻节点的祖先不一样时，在统一祖先时选择最小的作为祖先，不要随意选，这是题目要求，同时合并祖先时顺带也将频率合并一下，我们使用两个hash表，一个用来存放祖先，一个用来存放频率：

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, String> unionMap = new HashMap<>();
        for (String name : names) {     //统计频率
            int idx1 = name.indexOf('(');
            int idx2 = name.indexOf(')');
            int frequency = Integer.valueOf(name.substring(idx1 + 1, idx2));
            map.put(name.substring(0, idx1), frequency);
        }
        for (String pair : synonyms) {  //union同义词
            int idx = pair.indexOf(',');
            String name1 = pair.substring(1, idx);
            String name2 = pair.substring(idx + 1, pair.length() - 1);
            while (unionMap.containsKey(name1)) {   //找name1祖宗
                name1 = unionMap.get(name1);
            }
            while (unionMap.containsKey(name2)) {   //找name2祖宗
                name2 = unionMap.get(name2);
            }
            if(!name1.equals(name2)){   //祖宗不同，要合并
                int frequency = map.getOrDefault(name1, 0) + map.getOrDefault(name2, 0);    //出现次数是两者之和
                String trulyName = name1.compareTo(name2) < 0 ? name1 : name2;
                String nickName = name1.compareTo(name2) < 0 ? name2 : name1;
                unionMap.put(nickName, trulyName);      //小名作为大名的分支，即大名是小名的祖宗
                map.remove(nickName);       //更新一下数据
                map.put(trulyName, frequency);
            }
        }
        String[] res = new String[map.size()];
        int index = 0;
        for (String name : map.keySet()) {
            StringBuilder sb = new StringBuilder(name);
            sb.append('(');
            sb.append(map.get(name));
            sb.append(')');
            res[index++] = sb.toString();
        }
        return res;
    }