346 Chapter 8.Sorting void eclass(int nf[],int n,int lista[],int listb[],int m) Given m equivalences between pairs of n individual elements in the form of the input arrays lista[1..m]and listb[1..m],this routine returns in nf [1..n]the number of the equiv- alence class of each of the n elements,integers between 1 and n (not all such integers used). int 1,k,ji for (k=1;k<=n;k++)nf [k]=k; Initialize each element its own class for(1=1:1<=m;1++)[ For each piece of input information... j=lista[l]; while (nf[j]!j)j-nf[j]; Track first element up to its ancestor k=listbl]: while (nf [k]!k)k=nf [k]; Track second element up to its ancestor. if (j !=k)nf[j]=k; If they are not already related,make them for (j=1;j<=nij++) Final sweep up to highest ancestors. while (nf[j]!nf [nf [j]])nf[j]=nf [nf [j]]; Alternatively,we may be able to construct a function equiv(j,k)that returns a nonzero (true)value if elements j and k are related,or a zero(false)value if they are not.Then we want to loop over all pairs of elements to get the complete picture.D.Eardley has devised a clever way of doing this while simultaneously sweeping the tree up to high ancestors in a manner that keeps it current and obviates most of the final sweep phase: void eclazz(int nf[],int n,int (*equiv)(int,int)) 9▣ Given a user-supplied boolean function equiv which tells whether a pair of elements,each in the range 1...n,are related,return in nf [1..n]equivalence class numbers for each element. 9 int kk,jj; nf[1]=1; IENTIFIC for (jj=2;jj<-n;jj++){ Loop over first element of all pairs. nf[ii]=ii; for (kk=1;kk<=(jj-1);kk++){ Loop over second element of all pairs. to dir nf [kk]=nf [nf [kk]]; Sweep it up this much. if ((*equiv)(jj,kk))nf [nf [nf [kk]]]=jj; Good exercise for the reader to figure out why this much ancestry is necessary! 1920 COMPUTING(ISBN for (jj=1;jj<=n;jj++)nf [jj]=nf[nf[jj]]; Only this much sweeping is needed finally. Numerical Recipes 021 43108 CITED REFERENCES AND FURTHER READING: (outside Knuth,D.E.1968,Fundamental Algorithms,vol.1 of The Art of Computer Programming(Reading. MA:Addison-Wesley).82.3.3.[1] North Software. Sedgewick,R.1988,Algorithms,2nd ed.(Reading,MA:Addison-Wesley),Chapter 30. Ame346 Chapter 8. Sorting Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). void eclass(int nf[], int n, int lista[], int listb[], int m) Given m equivalences between pairs of n individual elements in the form of the input arrays lista[1..m] and listb[1..m], this routine returns in nf[1..n] the number of the equiv￾alence class of each of the n elements, integers between 1 and n (not all such integers used). { int l,k,j; for (k=1;k<=n;k++) nf[k]=k; Initialize each element its own class. for (l=1;l<=m;l++) { For each piece of input information... j=lista[l]; while (nf[j] != j) j=nf[j]; Track first element up to its ancestor. k=listb[l]; while (nf[k] != k) k=nf[k]; Track second element up to its ancestor. if (j != k) nf[j]=k; If they are not already related, make them } so. for (j=1;j<=n;j++) Final sweep up to highest ancestors. while (nf[j] != nf[nf[j]]) nf[j]=nf[nf[j]]; } Alternatively, we may be able to construct a function equiv(j,k) that returns a nonzero (true) value if elements j and k are related, or a zero (false) value if they are not. Then we want to loop over all pairs of elements to get the complete picture. D. Eardley has devised a clever way of doing this while simultaneously sweeping the tree up to high ancestors in a manner that keeps it current and obviates most of the final sweep phase: void eclazz(int nf[], int n, int (*equiv)(int, int)) Given a user-supplied boolean function equiv which tells whether a pair of elements, each in the range 1...n, are related, return in nf[1..n] equivalence class numbers for each element. { int kk,jj; nf[1]=1; for (jj=2;jj<=n;jj++) { Loop over first element of all pairs. nf[jj]=jj; for (kk=1;kk<=(jj-1);kk++) { Loop over second element of all pairs. nf[kk]=nf[nf[kk]]; Sweep it up this much. if ((*equiv)(jj,kk)) nf[nf[nf[kk]]]=jj; Good exercise for the reader to figure out why this much ancestry is necessary! } } for (jj=1;jj<=n;jj++) nf[jj]=nf[nf[jj]]; Only this much sweeping is needed } finally. CITED REFERENCES AND FURTHER READING: Knuth, D.E. 1968, Fundamental Algorithms, vol. 1 of The Art of Computer Programming (Reading, MA: Addison-Wesley), §2.3.3. [1] Sedgewick, R. 1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), Chapter 30