next up previous
Next: ASCII Art Up: UMD HPC98 Questions Previous: Line Interval Density

Garbage Collection

A common problem faced by programmers is the need to reuse dynamically allocated memory when it is no longer needed. One approach is to automatically detect such pieces of unusable memory (garbage) by tracking program pointers. This technique, known as garbage collection, is used in languages such as Lisp and Java.

As a systems programmer, it is your job to track statements executed by a program and determine what memory may be reused. All memory is allocated as cells which contain two pointers each ( tex2html_wrap_inline308 ). Cell pointers initially point nowhere, but may be pointed at specific cells through assignment statements.

A cell is considered to be garbage when it can no longer be accessed by a pointer from cell 1 (the main program's cell), or through a pointer from some cell accessible from cell 1. Cell 1 is never considered to be garbage. Your job is to track a number of assignment statements to cells, then decide which cells are garbage and may be reused.

Input Format

The first line of input will be n, the number of cells. The cells are numbered from 1 to n. Remaining lines will be a list of ordered triples (x,y,z) specifying an assignment of cell x's pointer y to cell z. The list is terminated by a triple where x = 0. You may assume there are a maximum of 50 cells.

Output Format

The output consists of one line. Output ``Garbage cells: " and the list of garbage cells found, in order from lowest to highest.



1 1 2
2 1 1
2 1 2
0 0 0


Garbage cells:  3


1 1 2
1 2 7
2 1 6
1 2 5
3 1 4
4 1 3
0 0 0


Garbage cells:   3  4  7  8

Test data used in judging

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4
Input 5 Output 5
Input 6 Output 6

Our solution

Chau-Wen Tseng
Tue Mar 24 16:22:12 EST 1998