1004. Counting Leaves (30)

考察樹結構的簡單存儲以及遍歷搜索 [cpp]   #include <iostream>   #include <vector>   #include <queue>      int n, m;   std::vector<std::vector<int>> edge;   std::vector<int> BFS(int s)   {       std::queue<std::pair<int,int>> q;       q.push(std::make_pair(s, 0));       int cur_step = 0;       std::vector<int> ans;       int cnt = 0;       while (!q.empty())       {           int u = q.front().first;           int step = q.front().second;           q.pop();           if(step > cur_step)           {               ans.push_back(cnt);               cnt = 0;               cur_step = step;           }           if(edge[u].size() == 0) cnt++;           for (int i = 0; i < edge[u].size(); ++i)           {               int v = edge[u][i];               q.push(std::make_pair(v, step+1));           }       }       ans.push_back(cnt);       return ans;   }   int main()   {       while (scanf("%d%d",&n,&m)!=EOF)       {           //input edges           edge.clear();           edge.resize(n+1);           while (m--)           {               int a, k;               scanf("%d%d", &a,&k);               while (k--)               {                   int b;                   scanf("%d",&b);                   edge[a].push_back(b);                   //edge[b].push_back(a);               }           }  www.2cto.com         std::vector<int> ans = BFS(1);           //output           for (int i = 0; i < ans.size(); ++i)           {               if(i != ans.size()-1)                   printf("%d ", ans[i]);               else printf("%d\n", ans[i]);           }       }       return  0;   }