RootedTree.cpp

#include <iostream>
#include <string>

struct {
	int parent;
	int child;
	int sibling;
} typedef node;


using namespace std;
const int NIL = -1;

node tree[10000];
int D[10000];

// Calculate depth of nodes
void depth(int u, int p)
{
	D[u] = p;
	if (tree[u].sibling != NIL)
		depth(tree[u].sibling, p);
	if (tree[u].child != NIL)
		depth(tree[u].child, ++p);
}

// MAIN FUNCTION
int main(int argc, char** argv)
{
	// Input
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		tree[i].child = tree[i].parent = tree[i].sibling = NIL;
	}
	int degree;
	int v;
	int s;
	int pre;
	for (int i = 0; i < n; i++) {
		cin >> v >> degree;
		for (int j = 0; j < degree; j++) {
			cin >> s;
			if (j == 0)
				tree[v].child = s;
			else
				tree[pre].sibling = s;
			pre = s;
			tree[s].parent = v;
		}
	}

	int r = 0;
	while (tree[r].parent != NIL)
		r = tree[r].parent;
	depth(r, 0);
	// Output
	for (int i = 0; i < n; i++) {
		cout << "node " << i << ":" << " parent = " << tree[i].parent << ", depth = " << D[i] << ", ";
		if (tree[i].parent == NIL)
			cout << "root, [";
		else if (tree[i].child == NIL)
			cout << "leaf, [";
		else
			cout << "internal node, [";
		r = tree[i].child;
		if (tree[i].child != NIL)
			cout << tree[i].child;
		while (tree[r].sibling != NIL && tree[i].child != NIL) {
			cout << ", " << tree[r].sibling;
			r = tree[r].sibling;
		}
		cout << "]" << endl;
	}

	return 0;
}