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.zzzyk.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;
}
补充：软件开发 , C++ ,
