AOJ ALDS1_7_A - Rooted Trees

根樹

題目網址

題意:

Rooted Trees是連接的，無環的，無向的圖。Rooted Trees是一種自由樹，其中一個頂點與另一個頂點是不同的。Rooted Trees的頂點稱為“節點”。
你的任務是編寫一個程序，為給定的根樹T的每個節點u報告以下信息：
node ID of u (節點編號)
parent of u (節點父親)
depth of u (節點深度)
node type (root, internal node or leaf)
a list of chidlren of u (列出節點小孩)

思路:

先創立一個結構parent、depth、type和internalNode方便紀錄我們的資料，接下來我們輸入每筆資料的時候就把自己節點的父親深度加一，就可以得到自己節點的深度，然後在子節點裡面，我們也做一樣的事情然後順便紀錄子節點的父親。

程式碼:

	#include<iostream>
	#include<cstdio>
	#include<vector>
	using namespace std;
	const int N = 100005;
	struct Node
	{
	string type;
	int parent;
	int depth;
	vector<int> internalNode;
	};
	void print(Node *graph, int n);
	int main()
	{
	int n, index, k, tmp;
	Node graph[N];
	cin >> n;
	for(int i = 0; i < n; i++){
	graph[i].parent = -1;
	}
	for(int i = 0; i < n; i++){
	cin >> index >> k;
	graph[index].depth = graph[graph[index].parent].depth + 1;
	for(int j = 0; j < k; j++){
	cin >> tmp;
	graph[index].internalNode.push_back(tmp);
	graph[tmp].parent = index;
	graph[tmp].depth = graph[graph[tmp].parent].depth + 1;
	}
	if(k){
	graph[index].type = "internal node";
	}else{
	graph[index].type = "leaf";
	}
	}
	print(graph, n);
	return 0;
	}
	void print(Node *graph, int n){
	for(int i = 0; i < n; i++){
	if(graph[i].parent == -1){
	graph[i].type = "root";
	}
	printf("node %d: parent = %d, depth = %d, ", i, graph[i].parent, graph[i].depth-1);
	cout << graph[i].type << ", [";
	for(int j = 0; j < graph[i].internalNode.size(); j++){
	if(j){
	printf(", %d", graph[i].internalNode[j]);
	}else{
	printf("%d", graph[i].internalNode[j]);
	}
	}
	printf("]\n");
	}
	}

view raw RootedTrees.cpp hosted with ❤ by GitHub