Instantly share code, notes, and snippets.

# tooshitaka/RootedTree.cpp Created Mar 10, 2017

What would you like to do?
 #include #include 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; }