11/*
2- * Author : joney_000[let_me_start][jaswantsinghyadav007 @gmail.com]
2+ * Author : joney_000[developer.jaswant @gmail.com]
33 * Algorithm : Disjoint Set Union O(log n) + path optimization
44 * Platform : Codeforces/Leetcode. eg. problem: https://leetcode.com/problems/satisfiability-of-equality-equations/
55 */
6- 76class DSU {
7+ private int [] parentOf ;
8+ private int [] depth ;
9+ private int size ;
10+ 11+ public DSU (int size ) {
12+ this .size = size ;
13+ this .depth = new int [size + 1 ];
14+ this .parentOf = new int [size + 1 ];
15+ clear (size );
16+ }
17+ 18+ // reset
19+ public void clear (int range ) {
20+ this .size = range ;
21+ for (int pos = 1 ; pos <= range ; pos ++) {
22+ depth [pos ] = 0 ;
23+ parentOf [pos ] = pos ;
24+ }
25+ }
826
927 // Time: O(log n), Auxiliary Space: O(1)
10- private int getRoot (int node , int [] parentOf ) {
28+ int getRoot (int node ) {
1129 int root = node ;
1230 // finding root
13- while (root != parentOf [root ]){
31+ while (root != parentOf [root ]){
1432 root = parentOf [root ];
1533 }
1634 // update chain for new parent
17- while (node != parentOf [node ]){
35+ while (node != parentOf [node ]){
1836 int next = parentOf [node ];
1937 parentOf [node ] = root ;
2038 node = next ;
2139 }
2240 return root ;
2341 }
2442
25- // Time: O(log n), Auxiliary Space: O(1)
26- private void joinSet (int a , int b , int [] parentOf , int [] depth ) {
27- int rootA = getRoot (a , parentOf );
28- int rootB = getRoot (b , parentOf );
29- if (rootA == rootB ){
43+ // Time: O(log n), Auxiliary Space: O(1)
44+ void joinSet (int a , int b ) {
45+ int rootA = getRoot (a );
46+ int rootB = getRoot (b );
47+ if (rootA == rootB ){
3048 return ;
3149 }
32- if (depth [rootA ] >= depth [rootB ]){
50+ if (depth [rootA ] >= depth [rootB ]){
3351 depth [rootA ] = Math .max (depth [rootA ], 1 + depth [rootB ]);
3452 parentOf [rootB ] = rootA ;
35- }else {
53+ }else {
3654 depth [rootB ] = Math .max (depth [rootB ], 1 + depth [rootA ]);
3755 parentOf [rootA ] = rootB ;
3856 }
3957 }
40- 41- private void joinSets (String [] equations , int [] parentOf , int [] depth ){
42- for (String equation : equations ){
43- int var1 = equation .charAt (0 ) - 'a' ;
44- int var2 = equation .charAt (3 ) - 'a' ;
45- char not = equation .charAt (1 );
46- if (not == '=' ){
47- joinSet (var1 , var2 , parentOf , depth );
48- }
49- }
50- }
51- // Time: O(log n), Auxiliary Space: O(1), PS: In this problem you will need constant space
52- // but in general you need to hold the info for each node's ancestors. that typically
53- // leads to O(N) auxiliary space
54- public boolean equationsPossible (String [] equations ) {
55- if (equations == null || equations .length <= 0 ){
56- return true ;
57- }
58- // disjoint sets
59- int []parentOf = new int [26 ];
60- int []depth = new int [26 ];
61- for (int pos = 0 ; pos < 26 ; pos ++){
62- depth [pos ] = 0 ;
63- parentOf [pos ] = pos ;
64- }
65- joinSets (equations , parentOf , depth );
66- for (String equation : equations ){
67- int var1 = equation .charAt (0 ) - 'a' ;
68- int var2 = equation .charAt (3 ) - 'a' ;
69- char not = equation .charAt (1 );
70- if (not == '!' ){
71- if (var1 == var2 ){
72- return false ;
73- }
74- if (getRoot (var1 , parentOf ) == getRoot (var2 , parentOf )){
75- return false ;
76- }
58+ 59+ int getNoOfTrees () {
60+ int uniqueRoots = 0 ;
61+ for (int pos = 1 ; pos <= size ; pos ++) {
62+ if (pos == getRoot (pos )) {
63+ uniqueRoots ++;// root
7764 }
7865 }
79- return true ;
66+ return uniqueRoots ;
8067 }
81- }
68+ }
0 commit comments