Computer Science CS50 Lecture Notes - Coefficient, Percolation Threshold, Monte Carlo Method
2 Jul 2022
School
Department
Course
Professor
Document Summary
This case shows that, how to improve algorithm step by step. We assume is connected to is an equivalence relation: Symmetric: if p is connected to q, then q is connected to p. Transitive: if p is connected to q and q is connected to r, then p is connected to r. Maximal set of objects that are mutually connected. https://cs. ericyy. me/algorithms-1/week-1/index. html. To merge components containing p and q, change all entries whose id equals id[p] to id[q]. Final solution: weighted quick-union with path compression quick-union: weighted: keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree. Keep the depth of any node x is at most lg n . path compression: make every other node in path point to its grandparent. Code: package week1; import common. stdin; import java. io. filenotfoundexception; import java. util. scanner; public class unionfind { Eric"s cs notes private int[] parent; private int[] sz; // record the weight.
