1: // Example 6.2: Firetruck
    2: 
    3: // Treat the map as a graph, where corners are nodes and streets are edges.
    4: // Read in all streets, building adjacency lists for each corner.
    5: // Then do a DFS for all paths from 1 to destination that do not contain
    6: // a loop (use mark seen nodes to prevent loops).
    7: 
    8: #include <iostream.h>
    9: #include <stdio.h>
   10: 
   11: struct {
   12:   int taint;
   13:   int adj[20];
   14:   int nadj;
   15: } corner[20];
   16: int paths;
   17: int path[20];
   18: int npath;
   19: 
   20: void print_paths(int a, int b) {
   21:   if (corner[a].taint) return;
   22:   if (a==b) {
   23:     for (int i=0; i<npath; i++)
   24:       printf("%-4d", path[i]+1);
   25:     printf("%d\n", b+1);
   26:     paths++;
   27:     return;
   28:   }
   29:   corner[a].taint = 1;
   30:   path[npath++] = a;
   31:   for (int i=0; i<corner[a].nadj; i++)
   32:     print_paths(corner[a].adj[i], b);
   33:   npath--;
   34:   corner[a].taint = 0;
   35: }
   36: 
   37: int main() {
   38:   int dest, count=1;
   39:   while (cin >> dest) {
   40:     dest--;
   41:     int i;
   42:     for (i=0; i<20; i++) corner[i].taint = corner[i].nadj = 0;
   43:     int a, b;
   44:     while (cin >> a >> b && a && b) {
   45:       a--, b--;
   46:       corner[a].adj[corner[a].nadj++] = b;
   47:       corner[b].adj[corner[b].nadj++] = a;
   48:     }
   49:     paths = npath = 0;
   50:     cout << "CASE " << count++ << ":" << endl;
   51:     print_paths(0, dest);
   52:     if (paths == 1)
   53:       cout << "There is 1 route from the firestation to streetcorner " <<
   54:         dest+1 << "." << endl;
   55:     else
   56:       cout << "There are " << paths <<
   57:         " routes from the firestation to streetcorner " << dest+1 << "." <<
   58:         endl;
   59:   }
   60:   return 0;
   61: }