USACO OPEN08 Problem 'coldwat' Analysis

by Rob Kolstad

This task presented a classic tree structure that required (recursive) traversal along with a counter that kept track of the tree's depth. Brazil's sophomore Andre Pereira submitted a classic solution; the comments are mine:

#include <cstdio>
#include <cstdlib>

using namespace std;

#define MAX 100001

int N, C;
int v[MAX][2];          /* the left and right subtree indexes */
int vis[MAX];           /* the distance from the root */

/* The 'DFS' (depth first search) routine is the recursive workhorse */

void DFS (int x){
  for (int i = 0; i < 2; i++)       /* both left and right branches */
    if (v[x][i] != 0 && vis[v[x][i]] == 0) {
                                    /* termination condition -- don't
continue if no branches */
      vis[v[x][i]] = vis[x] + 1;    /* this is the "I'm one farther deeper" marker */
      DFS (v[x][i]);                /* then continue deeper into the tree */
    }
}

int main(){
        /* initialization and input */
  freopen ("coldwat.in", "r", stdin);
  freopen ("coldwat.out", "w", stdout);
  scanf ("%d%d", &N, &C);

  for (int i = 0; i <= N; i++)
    v[i][0] = v[i][1] = 0;

  for (int i = 0; i < C; i++){
    int x, b1, b2;
    scanf ("%d%d%d", &x, &b1, &b2);
    v[x][0] = b1;
    v[x][1] = b2;
  }

        /* kick off the recursion */
  vis[1] = 1;
  DFS (1);

        /* print the results */
  for (int i = 1; i <= N; i++)
    printf ("%d\n", vis[i]);
  return 0;
}