AcWing 1476. 数叶子结点
原题链接
简单
作者:
_如鲸向海
,
2022-06-26 15:20:48
,
所有人可见
,
阅读 177
C++ 代码(甲级01day)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int h[N],e[N*N],ne[N*N],idx;//无双向边不需要记录st状态数组
typedef pair<int,int> PII;//用于记录节点的id和depth
queue<PII> q;
int n,m;
void add(int a,int b){//构建树
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void bfs(){
q.push({1,0});
int ans = 0,cur = 0;//cur存上一个访问节点的depth
while(q.size()){
auto t = q.front();
q.pop();
int depth = t.second;
int u = t.first;
if(cur<depth){//说明此时到了树的下一层,需要把ans输出;
cur = depth;
cout<<ans<<" ";
ans = 0;
}
//将子节点推入队列中
bool success = false;
for(int i = h[u];i!=-1;i = ne[i]){
int j = e[i];
q.push({j,depth+1});
success = true;
}
if(!success) ans++;//此时邻接表中除了表头无其他节点说明访问到了叶节点
}
cout<<ans<<" ";//最后的一层节点
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i = 0;i<m;i++){
string father;
int k = 0;
int id = 0;
cin>>father;
if(father[0] == '0') id = father[1] - '0';
else id = (father[0] - '0')*10 + father[1] - '0';
cin>>k;
for(int j = 0;j<k;j++){
int u;
string child;
cin>>child;
if(child[0] == '0') u = child[1] - '0';
else u = (child[0] - '0')*10 + child[1] - '0';
add(id,u);//构建树
}
}
bfs();
return 0;
}