Union find template and notes 

class UnionFind {
        int[] father;
        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        public int find(int n) {
            if (father[n] != n) father[n] = find(father[n]);
            return father[n];
        }

        public void union(int a, int b) {
            father[find(a)] = find(b);
        }

        public boolean query(int a, int b){
            return find(a) == find(b);
        }
    }
1. 融合不同的component


2. 判断环


3. 判断是否在一个group里面


Union find实现的关键是找father

评论

发表评论

此博客中的热门博文

5. Longest Palindromic Substring

Problem: Given a string  s , find the longest palindromic substring in  s . You may assume that the maximum length of  s  is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 5/22/2018 update: No need to think about after while loop, whether start and end are valid or not. Just update palindrome length within the loop. class Solution { int max = 1 ; int start = 0 ; public String longestPalindrome ( String s) { if (s == null || s . length() == 0 ) return "" ; for ( int i = 0 ; i < s . length() - 1 ; i ++ ) { computePalindrome(s, i, i); computePalindrome(s, i, i + 1 ); } return s . substring(start, start + max); } private void computePalindrome ( String s, int l, int r) { int temp = 0 , len = 0 ; while (l ...
阅读全文

Backpack IV

思路： 马甲题 state: dp[i][j],体积为j时，前i个物品能够占满j体积所需要的方法数。 transition: dp[i][j]+=dp[i-1][j]+dp[i-1][j-k*nums[i-1]], k>=0 && k*nums[i-1]<=j 实现： dp[i][0]需要设置初始值为1，表示体积为0时，前i个物品能取的方法数为1，就是不取。 方法2 ： 用一维数组来做dp[j]=dp[j]+dp[j-nums[i-1]],右边的dp[j]表示前i-1个物品能够取体积为j的方法，因为暂时没有更新。实现的时候是nums[i-1]<=j<=tagert，j是从小到大，因为这道题允许物品重复。在j-nums[i-1]>nums[i-1]这种情况下，dp[j-num[i-1]]就会被更新也就是重复的情况。
阅读全文