82 The Dynamic Equivalence Problem Given an equivalence relation decide for any a and b if a-b Example〗 Given s={1,2,3,4,5,6,7,8,9,10,1,12}and9 relations:12=4,3=1,6≡10,8=9,7=4,6=8,3=5,2=11,1l=12 The equivalence classes are ( 2, 4, 7,11, 123,(,, 5,(6,8,9,) Algorithm:(Union /Find) [ /step 1: read the relations in*/ Initialize n disjoint sets; while( read in a -b)i if(! (Find (a== Find(b)) Union the two sets: 3/*end-while*/ / step 2: decide if a-b*/ while( read in a and b) if Find(a= Find(b)output( true ) else output( false )§2 The Dynamic Equivalence Problem Given an equivalence relation ~, decide for any a and b if a ~ b. 〖Example〗 Given S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } and 9 relations: 124, 31, 610, 89, 74, 68, 35, 211, 1112. The equivalence classes are { 2, 4, 7, 11, 12 }, { 1, 3, 5 }, { 6, 8, 9, 10 } Algorithm: { /* step 1: read the relations in */ Initialize N disjoint sets; while ( read in a ~ b ) { if ( ! (Find(a) == Find(b)) ) Union the two sets; } /* end-while */ /* step 2: decide if a ~ b */ while ( read in a and b ) if ( Find(a) == Find(b) ) output( true ); else output( false ); } (Union / Find)