#include<stdio.h>
#include<algorithm>
#define max 101
using namespace std;
int family[max][max];
int allnode, non_leaf;
int no_leaf[max];//no_leaf=1表示该点是叶节点;
//顺序队列,用数组存储
//初始条件 front =rear=0
//满:rear=m 容量m
//空 front=rear
typedef struct
{
int data[max];
int front, rear;
}Queue;
//初始化队列
Queue InitQueue()
{
Queue p;
fill(p.data, p.data + max, 0);
p.front = p.rear = 0;
return p;
}
//插入
int InQueue(Queue* p, int e)
{
p->data[p->rear++] = e;
if (p->rear > max)
return 0;
else
{
return 1;
}
}
//删除
int DeQueue(Queue* p)
{
if (p->front == p->rear)
return 0;
else
{
p->front++; //将队头指针后移即可删除
return p->data[p->front-1];
}
}
void print(Queue*p1,Queue*p2) {
if (p1->data[p1->front] == 0 && p2->data[p2->front] == 0) return;
if (non_leaf == 0)return;
int root = DeQueue(p1);
int cout = 0;
while (root!=0) {//队列里空就是0 family里空是0 no_leaf里空是-1;
for (int j = 0; j < max; j++) {
if (family[root][j]) {
InQueue(p2, j);
if (no_leaf[j] == 0)cout++;
}
}
root = DeQueue(p1);
}
printf(" %d", cout);
non_leaf -= cout;
}
int main() {
Queue p1 = InitQueue();
Queue p2 = InitQueue();
scanf("%d", &allnode);
if (allnode == 0) {
return 0;
}
scanf("%d", &non_leaf);
fill(family[0], family[0]+101*101, 0);
fill(no_leaf, no_leaf + max, -1);
int name = 0;
int children = 0;
int childname = 0;
for (int i = 0; i < non_leaf; i++) {
scanf("%d%d", &name, &children);
no_leaf[name] = 1;
for (int k = 0; k < children; k++) {
scanf("%d", &childname);
family[name][childname] = 1;
if (no_leaf[childname] != 1)
{
no_leaf[childname] = 0;
}
}
}
if (allnode == 1) {
printf("%d", 1);
return 0;
}
else printf("%d", 0);
InQueue(&p1, 1);
while(p1.data[p1.front]!=0||p2.data[p2.front]!=0)
{
print(&p1, &p2);
print(&p2, &p1);
if (non_leaf == 0)return 0;
}
}
做完发现我的做法还蛮特立独行
用队列进行层序遍历,用两个数组来回入队列,每次入一层队列然后输出当层的叶节点个数。
用了各种数据测试都没问题 但是pat上只对了一组数据。如果不改变方法 该怎么改对呢。