明年本科毕业刷题贴

802.    Reverse graph做法时间和空间复杂度过高，明天需要补学Graph Coloring做法。
210.    topological ordering.
回归graph（作业太多只配做两题。贵在坚持

399 Union Find问题。 路径压缩是难点

补充内容 (2022-10-19 13:51 +8:00):
int x, int y, value
int rootX = find(x);
int rooY = find(y);
parent[rootX] = rootY;
weight[rootX] = weight[y]* value / weight[x]

839 (hard) Similar String Groups 难度甚至比不上399.
主要注意的点在于初始化 sol为n。每次union把 sol -1。如果每次union+1，合并到同一个组的情况会让结果变大。 用的还是union find。

补充内容 (2022-10-20 09:24 +8:00):
952 (Hard) Largest Component Size by Common Factor 同样使用的uf. 由于每个数需要计算整除factor， 需要优化 factor loop stop          when reach sqrt(max int).

990. Satisfiability of Equality Equations (Medium) 写了一大串unionFind结果出了bug。 判断时只需要先把 =的union， 然后再看 != 是否存在union即可

补充内容 (2022-10-21 13:56 +8:00):
721. Accounts Merge (Medium) DSU

DSU 题目总结:  利用index代替String来union。最后在input里面找到index对应的String存入答案返回。 题目关键是找到Union两者之间的对应关系，以此判断是否需要union。 题目压缩部分可以采用根据 size判断root节点。

737. Sentence Similarity II (Medium)没看答案写了10分钟，还是union find的问题。 String compare在java里面应该要用 str1.equals(str2) 卡了bug，还有conner case 看 str1 和 str2 的length没考虑到，导致index off range。 总体做了这么多union find已经掌握了技巧。

DSU（unionFind）class implementation:
    private class DSU{
        private int [] parent;
        public DSU(int n){
            parent = new int[n];
            for(int i = 0; i < n ; i++ ){
                parent[i] = i;
            }
        }
        
        public void union(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) return;
            parent[rootX] = rootY;
        }
        
        public int find(int x){
            if(parent[x] == x) return x;
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
根据问题可以加入 weight 和 size 进行优化使用。

新Topic(Bipartite)
785. Is Graph Bipartite? (medium) 用dfs coloring。难度不大

补充内容 (2022-10-22 15:09 +8:00):
886. Possible Bipartition (medium) DSU比较慢，DFS解法

补学了一下 886。给出的list要用adjacency list先把图存下来，后续和之前的graph用一样的模板就行. disjoint set的解法可以用类似解答

补充内容 (2022-10-23 18:26 +8:00):
https://leetcode.com/playground/Rbrs6cVQ
趁半夜卷了一题朋友发的OA

1042. Flower Planting With No Adjacent 不靠答案写出了自己的 beats 90%答案。Graph开始有点顿悟了

补充内容 (2022-10-24 09:45 +8:00):
997. Find the Town Judge