{"id":703,"date":"2019-09-08T22:30:54","date_gmt":"2019-09-08T14:30:54","guid":{"rendered":"http:\/\/149.129.74.185\/?p=703"},"modified":"2019-09-08T23:25:17","modified_gmt":"2019-09-08T15:25:17","slug":"patadvanced1004-counting-leaves-30-%e5%88%86","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=703","title":{"rendered":"PAT(Advanced)1004 Counting Leaves (30 \u5206)"},"content":{"rendered":"

1004<\/span>\u00a0<\/span>Counting Leaves<\/span>\u00a0<\/span>(30\u00a0<\/span>\u5206<\/span>)<\/span><\/h2>\n

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.<\/p>\n

Input Specification:<\/h3>\n

Each input file contains one test case. Each case starts with a line containing\u00a0<\/span><\/span><\/span>0<\/span><<\/span>N<\/span><<\/span>1<\/span>0<\/span>0<\/span><\/span><\/span><\/span>, the number of nodes in a tree, and\u00a0<\/span><\/span><\/span>M<\/span><\/span><\/span><\/span>\u00a0<\/span>(<\/span><\/span><<\/span>N<\/span><\/span><\/span><\/span>), the number of non-leaf nodes. Then\u00a0<\/span><\/span><\/span>M<\/span><\/span><\/span><\/span>\u00a0<\/span>lines follow, each in the format:<\/p>\n

ID K ID[1] ID[2] ... ID[K]\r\n<\/code><\/pre>\n
where\u00a0<\/span>ID<\/code>\u00a0<\/span>is a two-digit number representing a given non-leaf node,\u00a0<\/span>K<\/code>\u00a0<\/span>is the number of its children, followed by a sequence of two-digit\u00a0<\/span>ID<\/code>‘s of its children. For the sake of simplicity, let us fix the root ID to be\u00a0<\/span>01<\/code>.<\/p>\n
The input ends with\u00a0<\/span><\/span><\/span>N<\/span><\/span><\/span><\/span>\u00a0<\/span>being 0. That case must NOT be processed.<\/p>\n
Output Specification:<\/h3>\n
For each test case, you are supposed to count those family members who have no child\u00a0<\/span>for every seniority level<\/strong>\u00a0<\/span>starting 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.<\/p>\n
The sample case represents a tree with only 2 nodes, where\u00a0<\/span>01<\/code>\u00a0<\/span>is the root and\u00a0<\/span>02<\/code>\u00a0<\/span>is its only child. Hence on the root\u00a0<\/span>01<\/code>\u00a0<\/span>level, there is\u00a0<\/span>0<\/code>\u00a0<\/span>leaf node; and on the next level, there is\u00a0<\/span>1<\/code>\u00a0<\/span>leaf node. Then we should output\u00a0<\/span>0 1<\/code>\u00a0<\/span>in a line.<\/p>\n
Sample Input:<\/h3>\n
2 1\r\n01 1 02\r\n<\/code><\/pre>\n
Sample Output:<\/h3>\n
0 1<\/code><\/pre>\n
\u9898\u76ee\u89e3\u8bfb\uff1a\u8f93\u5165\u4e00\u4e32\u6811\u7684\u8282\u70b9\uff0c\u53ca\u8fd9\u4e9b\u8282\u70b9\u7684\u5b69\u5b50\u7684\u7f16\u53f7\uff0c01\u4e3a\u8ddf\u8282\u70b9\uff0c\u8f93\u51fa\u6bcf\u4e00\u5c42\u7684\u53f6\u8282\u70b9\u4e2a\u6570\u3002<\/p>\n
\u89e3\u9898\u601d\u8def\uff1a\u7528vector<int> T[100]\uff0c\u5c31\u662f\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u50a8\u5b58\u53f6\u8282\u70b9\u548c\u5b69\u5b50\u7684\u7f16\u53f7\uff0c\u6709\u70b9\u50cf\u5b58\u56fe\u7684\u8fb9\u3002\u8fd9\u9053\u9898\u65b9\u4fbf\u7684\u5c31\u662f01\u4e00\u5b9a\u662f\u6839\u8282\u70b9\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5DFS\u5f97\u5230\u6bcf\u4e2a\u8282\u70b9\u7684\u9ad8\u5ea6\uff0c\u628a\u6ca1\u6709\u5b69\u5b50\u7684\u8282\u70b9\u6309\u5c42\u8bb0\u6570\uff0c\u56e0\u4e3a\u4e2d\u95f4\u53ef\u80fd\u6709\u5f88\u591a0\uff0c\u6240\u4ee5\u8bb0\u5f55\u4e00\u4e0b\u6700\u6df1\u5c42\u3002\u8fd9\u6b21\u5361\u5728\u4e86\u9012\u5f52\u91cc\u7684++deep\uff0cdeep++\u6bcf\u4e00\u6b21\u90fd\u4f1a\u7ed9deep+1\uff0c\u4f46\u5176\u5b9e\u6211\u8981\u7684\u5c31\u662fdeep+1\uff0c\u614e\u7528++\u7684\u64cd\u4f5c\u3002<\/p>\n
<\/p>\n
AC\u4ee3\u7801<\/p>\n
#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\nint leave[100];\r\nvector<int> T[100];\r\nint n,m;\r\nint maxdep = 0;\r\nvoid DFS(int root,int deep){\r\n    if(T[root].size() == 0 )leave[deep]++;\r\n    if(maxdep<deep)\r\n        maxdep = deep;\r\n    for( int i = 0 ; i < T[root].size() ; i ++ ){\r\n        DFS(T[root][i],deep+1);\r\n    }\r\n}\r\n\r\nint main(int argc, const char * argv[]) {\r\n    cin >> n >> m;\r\n    int ID,k,c;\r\n    for( int i = 0 ; i < m ; i ++ ){\r\n        cin >> ID >> k;\r\n        for( int j = 0 ; j < k; j ++ ){\r\n            cin >> c;\r\n            T[ID].push_back(c);\r\n        }\r\n    }\r\n    DFS(1,0);\r\n    for( int i = 0 ; i < maxdep ; i ++ ){\r\n        cout << leave[i] << \" \";\r\n    }\r\n    cout << leave[maxdep];\r\n    \/\/std::cout << \"Hello, World!\\n\";\r\n    return 0;\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1004\u00a0Counting Leaves\u00a0(30\u00a0\u5206) A family hierarchy is  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,18,17],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/703"}],"collection":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=703"}],"version-history":[{"count":4,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/703\/revisions"}],"predecessor-version":[{"id":707,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/703\/revisions\/707"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=703"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=703"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}