1004. Counting Leaves (30)

ID K ID[1] ID[2] ... ID[K]

2 1
01 1 02

0 1

======================================================
恩恩，数叶子，倒腾了一晚上，一直报段错误，最后知道真相的我眼泪掉下来》。。
原来是指针指来指去，本来要指子节点的ID结果弄成了自己的ID，然后数组就不对了》。。
思路比较简单，他要hierarchy，我们就搞一个
他要Node，我们就弄个结构给他
Node之间用指针传上就行了..虽然带两个*号的东西好久没用了，但是心里想着这货是指针的数组就行了…
为了节约时间，最后找结果的时候用的静态数组100*100，比较无耻，反正题目给够了内存…
每一行计算的时候，把自己的孩子加到数组的下一行里面，搜索到世界的尽头…然后就结束了
=======================================================

#include 
using namespace std;
struct Node
{
	Node **childNodes; //array of ptrChilds
	int ID; //ID  = array index + 1 ??
	int childSize;
	int nowIndex; //If nowIndex ==0 , this node must be a childless one.
	//int level; //root level = 0
	Node(int id, int cSize = 100)
	{
		ID = id;
		childSize = cSize;
		childNodes = new Node*[childSize];
		nowIndex = 0;
	}
	bool insertChildNode(Node* pNode)
	{
		if(nowIndex > childSize)
		{
			cerr << "child over size!" << endl;
			return false;
		}
		childNodes[nowIndex++] = pNode;
		return true;
	}
};
static int M,N;
static Node** allNodes;
static int lvls[100][100] = {0};
int main()
{
	//--First line
	cin >> N;
	cin >> M;
	//--init Node* array
	if(N == 0 || M == 0)
	{
		cout << "1";
		return 0;
	}
//We presume that there is no gap between IDs (eg: 01 02 05 06 07)
//otherwise we need to create more new Nodes
	allNodes = new Node*[N];
	for(int i=0; ilevel = 0; //root node level
	//--read M lines for the child info
	int id, K;
	for(int line=0; line> id;
		id--;  //turn to the index
		Node* pParent = allNodes[id];
		cin >> K;
		int cId;
		while(K > 0)
		{
			//link every child
			cin >> cId;
			cId --;
			pParent->insertChildNode(allNodes[cId]);
			K--;
		}
	}
	//--finished reading
	Node* root = allNodes[0];
	//--init first line
	if(root->nowIndex == 0)
	{
		cout << 1;
		return 0;
	}
	else
	{
		cout << 0;
	}
	for(int i=0; inowIndex ; i++)
	{
		Node* childNode = root->childNodes[i];
		lvls[0][i] =childNode->ID -1;
	}
	//GOGOGO!!!
	int row=0, col=0;
	int nextColOffset = 0;
	int count = 0;
	while(true)
	{
		int posNow = lvls[row][col];
		if( posNow == 0)
		{
			if(col == 0)			//end of all things
				break;
			row ++;
			col = 0;
			cout << " " << count;
			count = 0; //reset line count
			nextColOffset = 0;
			continue; //move to the head of next line
		}
		Node* now = allNodes[posNow];
		if(now->nowIndex <= 0)
			count ++;
		else
		{
			//put its children into next line
			for(int i=0; inowIndex; i++)
			{
				lvls[row+1][nextColOffset++] = now ->childNodes[i] ->ID -1;
			}
		}
		col ++;
	}
	return 0;
}