{"id":65,"date":"2013-03-15T21:31:02","date_gmt":"2013-03-15T13:31:02","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=65"},"modified":"2013-03-15T21:31:02","modified_gmt":"2013-03-15T13:31:02","slug":"1004-counting-leaves-30","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=65","title":{"rendered":"1004. Counting Leaves (30)"},"content":{"rendered":"

1004. Counting Leaves (30)<\/h1>\n
\n
\n
\u65f6\u95f4\u9650\u5236<\/div>\n
400 ms<\/div>\n<\/div>\n
\n
\u5185\u5b58\u9650\u5236<\/div>\n
32000 kB<\/div>\n<\/div>\n
\n
\u4ee3\u7801\u957f\u5ea6\u9650\u5236<\/div>\n
16000 B<\/div>\n<\/div>\n
\n
\u5224\u9898\u7a0b\u5e8f<\/div>\n
Standard<\/div>\n<\/div>\n
\u4f5c\u8005<\/div>\n
CHEN, Yue<\/div>\n<\/div>\n
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. 
\nInput<\/b>
\nEach input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:<\/p>\n
ID K ID[1] ID[2] ... ID[K]<\/pre>\n
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01. 
\nOutput<\/b>
\nFor each test case, you are supposed to count those family members who have no child\u00a0for every seniority level<\/b>\u00a0starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
\nThe sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.
\nSample Input<\/b><\/p>\n
2 1\n01 1 02<\/pre>\n
Sample Output<\/b><\/p>\n
0 1<\/pre>\n<\/div>\n
======================================================
\n\u6069\u6069\uff0c\u6570\u53f6\u5b50\uff0c\u5012\u817e\u4e86\u4e00\u665a\u4e0a\uff0c\u4e00\u76f4\u62a5\u6bb5\u9519\u8bef\uff0c\u6700\u540e\u77e5\u9053\u771f\u76f8\u7684\u6211\u773c\u6cea\u6389\u4e0b\u6765\u300b\u3002\u3002
\n\u539f\u6765\u662f\u6307\u9488\u6307\u6765\u6307\u53bb\uff0c\u672c\u6765\u8981\u6307\u5b50\u8282\u70b9\u7684ID\u7ed3\u679c\u5f04\u6210\u4e86\u81ea\u5df1\u7684ID\uff0c\u7136\u540e\u6570\u7ec4\u5c31\u4e0d\u5bf9\u4e86\u300b\u3002\u3002
\n\u601d\u8def\u6bd4\u8f83\u7b80\u5355\uff0c\u4ed6\u8981hierarchy\uff0c\u6211\u4eec\u5c31\u641e\u4e00\u4e2a
\n\u4ed6\u8981Node\uff0c\u6211\u4eec\u5c31\u5f04\u4e2a\u7ed3\u6784\u7ed9\u4ed6
\nNode\u4e4b\u95f4\u7528\u6307\u9488\u4f20\u4e0a\u5c31\u884c\u4e86..\u867d\u7136\u5e26\u4e24\u4e2a*\u53f7\u7684\u4e1c\u897f\u597d\u4e45\u6ca1\u7528\u4e86\uff0c\u4f46\u662f\u5fc3\u91cc\u60f3\u7740\u8fd9\u8d27\u662f\u6307\u9488\u7684\u6570\u7ec4\u5c31\u884c\u4e86…
\n\u4e3a\u4e86\u8282\u7ea6\u65f6\u95f4\uff0c\u6700\u540e\u627e\u7ed3\u679c\u7684\u65f6\u5019\u7528\u7684\u9759\u6001\u6570\u7ec4100*100\uff0c\u6bd4\u8f83\u65e0\u803b\uff0c\u53cd\u6b63\u9898\u76ee\u7ed9\u591f\u4e86\u5185\u5b58…
\n\u6bcf\u4e00\u884c\u8ba1\u7b97\u7684\u65f6\u5019\uff0c\u628a\u81ea\u5df1\u7684\u5b69\u5b50\u52a0\u5230\u6570\u7ec4\u7684\u4e0b\u4e00\u884c\u91cc\u9762\uff0c\u641c\u7d22\u5230\u4e16\u754c\u7684\u5c3d\u5934…\u7136\u540e\u5c31\u7ed3\u675f\u4e86
\n=======================================================<\/p>\n
\n#include \nusing namespace std;\nstruct Node\n{\n\tNode **childNodes; \/\/array of ptrChilds\n\tint ID; \/\/ID  = array index + 1 ??\n\tint childSize;\n\tint nowIndex; \/\/If nowIndex ==0 , this node must be a childless one.\n\t\/\/int level; \/\/root level = 0\n\tNode(int id, int cSize = 100)\n\t{\n\t\tID = id;\n\t\tchildSize = cSize;\n\t\tchildNodes = new Node*[childSize];\n\t\tnowIndex = 0;\n\t}\n\tbool insertChildNode(Node* pNode)\n\t{\n\t\tif(nowIndex > childSize)\n\t\t{\n\t\t\tcerr << \"child over size!\" << endl;\n\t\t\treturn false;\n\t\t}\n\t\tchildNodes[nowIndex++] = pNode;\n\t\treturn true;\n\t}\n};\nstatic int M,N;\nstatic Node** allNodes;\nstatic int lvls[100][100] = {0};\nint main()\n{\n\t\/\/--First line\n\tcin >> N;\n\tcin >> M;\n\t\/\/--init Node* array\n\tif(N == 0 || M == 0)\n\t{\n\t\tcout << \"1\";\n\t\treturn 0;\n\t}\n\/\/We presume that there is no gap between IDs (eg: 01 02 05 06 07)\n\/\/otherwise we need to create more new Nodes\n\tallNodes = new Node*[N];\n\tfor(int i=0; ilevel = 0; \/\/root node level\n\t\/\/--read M lines for the child info\n\tint id, K;\n\tfor(int line=0; line> id;\n\t\tid--;  \/\/turn to the index\n\t\tNode* pParent = allNodes[id];\n\t\tcin >> K;\n\t\tint cId;\n\t\twhile(K > 0)\n\t\t{\n\t\t\t\/\/link every child\n\t\t\tcin >> cId;\n\t\t\tcId --;\n\t\t\tpParent->insertChildNode(allNodes[cId]);\n\t\t\tK--;\n\t\t}\n\t}\n\t\/\/--finished reading\n\tNode* root = allNodes[0];\n\t\/\/--init first line\n\tif(root->nowIndex == 0)\n\t{\n\t\tcout << 1;\n\t\treturn 0;\n\t}\n\telse\n\t{\n\t\tcout << 0;\n\t}\n\tfor(int i=0; inowIndex ; i++)\n\t{\n\t\tNode* childNode = root->childNodes[i];\n\t\tlvls[0][i] =childNode->ID -1;\n\t}\n\t\/\/GOGOGO!!!\n\tint row=0, col=0;\n\tint nextColOffset = 0;\n\tint count = 0;\n\twhile(true)\n\t{\n\t\tint posNow = lvls[row][col];\n\t\tif( posNow == 0)\n\t\t{\n\t\t\tif(col == 0)\t\t\t\/\/end of all things\n\t\t\t\tbreak;\n\t\t\trow ++;\n\t\t\tcol = 0;\n\t\t\tcout << \" \" << count;\n\t\t\tcount = 0; \/\/reset line count\n\t\t\tnextColOffset = 0;\n\t\t\tcontinue; \/\/move to the head of next line\n\t\t}\n\t\tNode* now = allNodes[posNow];\n\t\tif(now->nowIndex <= 0)\n\t\t\tcount ++;\n\t\telse\n\t\t{\n\t\t\t\/\/put its children into next line\n\t\t\tfor(int i=0; inowIndex; i++)\n\t\t\t{\n\t\t\t\tlvls[row+1][nextColOffset++] = now ->childNodes[i] ->ID -1;\n\t\t\t}\n\t\t}\n\t\tcol ++;\n\t}\n\treturn 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
1004. Counting Leaves (30) \u65f6\u95f4\u9650\u5236 400 ms \u5185\u5b58\u9650\u5236 32000 kB \u4ee3\u7801\u957f\u5ea6\u9650\u5236 16000 B \u5224\u9898\u7a0b\u5e8f Standard \u4f5c\u8005 CHEN, Yue A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.  Input Each input file contains one test case. Each case starts with a line containing […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-65","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/65","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=65"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=65"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=65"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=65"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}