home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume17 / contest-prog / part02 / prob16.txt < prev    next >
Encoding:
Text File  |  1989-02-06  |  1.0 KB  |  22 lines
  1. Problem 16: Equivalence classes.
  2.  
  3.  
  4. Suppose that we have a set of N objects {a[i]}.  We are also given M statements
  5. of the form a[i]  == a[j]  .  Let us assume that the objects have been mapped into
  6. the integers 1 .. N by some manner.  For example, with N = 19 and M = 16, we
  7. might have the following objects and relationships:
  8.        18 = 12        16 = 14         8 = 18        16 =  6
  9.         6 = 10         9 =  1        17 =  4        16 = 17
  10.         8 =  2         3 = 13         9 = 11         3 =  8
  11.        11 =  5         7 = 19         3 =  9        19 = 15
  12. Write a program that reads M and N, followed by the M pairings i = j,
  13. with i and j both in the range 1 .. N.  Your program should compute which
  14. objects fall into which classes of equivalent objects, and should then
  15. print out these classes, as follows:  objects sorted within each class,
  16. and classes printed in order of their first members.  Thus, for the example
  17. above, the output would be:
  18.           1   2   3   5   8   9  11  12  13  18
  19.           4   6  10  14  16  17
  20.           7  15  19
  21.  
  22.