uopspop

Untitled

Jul 31st, 2021
930
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3.     Map<Integer, Integer> node2root = new HashMap<>();
  4.     public void union(Integer num1, Integer num2) {
  5.         add(num1);
  6.         add(num2);
  7.        
  8.         Integer root1 = find_root(num1);
  9.         Integer root2 = find_root(num2);
  10.        
  11.         if (root1 == root2) return;
  12.        
  13.         node2root.put(root1, root2);
  14.     }
  15.    
  16.     public void add(Integer num1) {
  17.         if (node2root.containsKey(num1)) return;
  18.         node2root.put(num1, num1);
  19.     }
  20.    
  21.     public Integer find_root(Integer num1) {
  22.         Integer root_now = node2root.get(num1);
  23.         if (root_now == num1) return num1;
  24.        
  25.         node2root.put(num1, find_root(root_now)); // attention: put root_now here instead of num1 again
  26.        
  27.         return node2root.get(num1);
  28.     }
  29.    
  30.     public boolean validTree(int n, int[][] edges) {
  31.         // a tree has exact (n - 1) edges.
  32.         if (edges.length != (n - 1)) return false;
  33.        
  34.         // initialize
  35.         for (int num_now = 0; num_now < n ;num_now++) {
  36.             add(num_now);
  37.         }
  38.        
  39.         // union
  40.         for (int i = 0; i < edges.length ;i++) {
  41.             int[] edge = edges[i];
  42.             int num1 = edge[0];
  43.             int num2 = edge[1];
  44.            
  45.             union(num1, num2);        
  46.         }
  47.        
  48.         // check if there are > 1 roots
  49.         Integer root_prev = null;
  50.         for (int num_now = 0; num_now < n ;num_now++) {
  51.             Integer root = find_root(num_now);
  52.            
  53.             if (root_prev != null) {
  54.                 if (root_prev != root) {
  55.                     return false;
  56.                 }
  57.             }
  58.            
  59.             root_prev = root;
  60.         }
  61.        
  62.         return true;
  63.     }
  64. }
RAW Paste Data