1: // Homework 6.2: Calling Circles
    2: 
    3: // Build a matrix with 1's indicating (directed) adjacencies between
    4: // two people/nodes.  Then iterate through setting all indirectly reachable
    5: // nodes as adjacent.
    6: // Then for each person print out who is reachable, removing/marking
    7: // each person printed.  Continue until each person has been printed.
    8: 
    9: #include <iostream.h>
   10: 
   11: typedef char name[26];
   12: 
   13: name person[25];
   14: int npeople = 0;
   15: int call_matrix[25][25];
   16: 
   17: int find_person(char *who) {
   18:   for (int i=0; i<npeople; i++)
   19:     if (!strcmp(person[i], who)) return i;
   20:   return -1;
   21: }
   22: 
   23: int add_person(char *who) {
   24:   strcpy(person[npeople], who);
   25:   return npeople++;
   26: }
   27: 
   28: int main() {
   29:   int junk, ncalls, count=0;
   30:   while (cin >> junk >> ncalls && junk && ncalls) {
   31:     npeople = 0;
   32:     int i, x, y, z;
   33:     for (x=0; x<25; x++)
   34:       for (y=0; y<25; y++)
   35:         call_matrix[x][y] = 0;
   36:     for (i=0; i<ncalls; i++) {
   37:       name buf1, buf2;
   38:       int p1, p2;
   39:       cin >> buf1 >> buf2;
   40:       if ((p1 = find_person(buf1)) == -1) p1 = add_person(buf1);
   41:       if ((p2 = find_person(buf2)) == -1) p2 = add_person(buf2);
   42:       call_matrix[p1][p2] = 1;
   43:     }
   44:     int flag = 1;
   45:     while (flag) {
   46:       flag = 0;
   47:       for (x=0; x<npeople; x++)
   48:         for (y=0; y<npeople; y++)
   49:           for (z=0; z<npeople; z++)
   50:             if (call_matrix[x][y] && call_matrix[y][z]
   51:              && !call_matrix[x][z]) {
   52:               call_matrix[x][z] = 1;
   53:               flag = 1;
   54:             }
   55:     }
   56:     if (count > 0) cout << endl;
   57:     cout << "Calling circles for data set " << ++count << ":" << endl;
   58:     for (i=0; i<npeople; i++) {
   59:       if (!*person[i]) continue;
   60:       cout << person[i];
   61:       for (x=i+1; x<npeople; x++)
   62:         if (*person[x] && call_matrix[i][x] && call_matrix[x][i]) {
   63:           cout << ", " << person[x];
   64:           *person[x] = '\0';
   65:         }
   66:       cout << endl;
   67:     }
   68:   }
   69:   return 0;
   70: }