昨天周赛T4是个很有意思的图论题，虽然题目本身的数据量用完全暴力的重复最小生成树计算就可以ac。不过我看了一下评论区的大佬，借鉴了他们O(mlogm)的算法思路，然后自己编写了一遍，所有的内容基本都在bobo老师的课程里囊括了，包括：

1. 最小生成树，使用Kruskal思路
2. 求桥，使用tarjan算法(就是ord，low两个数组)
   不过其中也有一些需要注意的地方，这个题需要自己多次建图，并且每次建图都可能出现自环边和平行边，这两个地方跟课程不太一样（花了好多时间想清楚这两个问题）。

具体思路大概是：

1. 按权值大小分组所有边
2. 从小到大枚举所有组，使用 tarjan算法找到当前组与之前所有被缩点形成的这个图的桥
3. 找完后对这个组中相同联通分量的组进行缩点（具体就是一个联通分量会被看作一个点）
4. 重复2，3直到结束

ps：因为此题是个人自从学完bobo老师的课程之后第一次做到求图的桥相关的题(本人暂时只做leetcode上的题)，深感此类题目的稀有，所以分享一下希望能够帮助到大家练习。

下面是代码：

class Solution {
    private class UF{
        int[] size;
        int[] parent;
        public UF(int n){
            size = new int[n];
            parent = new int[n];

            Arrays.fill(size, 1);
            Arrays.setAll(parent, i -> i);
        }

        public int find(int i){
            if(i != parent[i])
                parent[i] = find(parent[i]);
            return parent[i];
        }

        public boolean isConnected(int i, int j){
            return find(i) == find(j);
        }

        public void union(int i, int j){
            int ir = find(i);
            int jr = find(j);
            if(ir == jr) return;

            if(size[ir] < size[jr]){
                parent[ir] = jr;
                size[jr] += size[ir];
            }else{
                parent[jr] = ir;
                size[ir] += size[jr];
            }
        }
    }
    private class Edge{
        int index;
        int[] edge;
        public Edge(int index, int[] edge){
            this.index = index;
            this.edge = edge;
        }
    }
    private List<Integer> y;
    private HashSet<Integer> no;
    private int n, cnt;
    private int[] ord, low;
    private boolean[] visited;
    private UF uf;
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {

        this.n = n;

        //优先队列用来给边按权值分组
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> e1.edge[2] - e2.edge[2]);
        for(int i = 0; i < edges.length; i ++)
            pq.add(new Edge(i, edges[i]));

        y = new ArrayList<>();
        no = new HashSet<>(); //由于非关键边可能会被重复加入，这里用个集合来存储

        uf = new UF(n);
        while(!pq.isEmpty()){
            int w = pq.peek().edge[2];
            HashSet<Integer> set = new HashSet<>(); //存储所有即将被遍历的图中的节点
            HashMap<Integer, List<Edge>> g = new HashMap<>(); //处理该组所用的图
            while(!pq.isEmpty() && pq.peek().edge[2] == w){
                Edge e = pq.poll();
                if(uf.isConnected(e.edge[0], e.edge[1])) continue; //去掉自环边

                g.computeIfAbsent(uf.find(e.edge[0]), ArrayList::new);
                g.computeIfAbsent(uf.find(e.edge[1]), ArrayList::new);

                List<Edge> list1 = g.get(uf.find(e.edge[0]));
                List<Edge> list2 = g.get(uf.find(e.edge[1]));

                list1.add(e);
                list2.add(e);
                set.add(e.edge[0]);
                set.add(e.edge[1]);
            }

            //tarjan重置各种变量
            cnt = 1;
            ord = new int[n];
            low = new int[n];
            visited = new boolean[n];
            
            for(int v: set)
                if(!visited[uf.find(v)]) dfs(uf.find(v), null, g);
            
            //找到所有关键边之后，将各个连通分量缩为一点
            for(int key: g.keySet())
                for(Edge e: g.get(key))
                    uf.union(e.edge[0], e.edge[1]);
        }

        List<List<Integer>> res = new ArrayList<>();
        res.add(y);
        res.add(new ArrayList<>(no));
        return res;
    }

    //tarjan求桥
    private void dfs(int v, Edge edge, HashMap<Integer, List<Edge>> g){
        
        ord[v] = low[v] = ++cnt;
        visited[v] = true;

        for(Edge e: g.get(v)){
            int next = uf.find(e.edge[0]) == v ? uf.find(e.edge[1]) : uf.find(e.edge[0]);
            if(!visited[next]){
                dfs(next, e, g);

                low[v] = Math.min(low[v], low[next]);

                if(low[next] > ord[v]) y.add(e.index);
                else no.add(e.index);
            }else if(e != edge){ //可能存在平行边，这里用之前一条边代替“父亲节点”
                low[v] = Math.min(low[v], low[next]);
                
                no.add(e.index);
            }
        }
    }
}