1004 Counting Leaves (30)(30 分)

DFS:因为要知道有多少层,每次进DFS先更新一下最大层数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 110;
vector<int>node[maxn];
int n, m;
int Layer[maxn];
int maxlayer = 0;
void DFS(int index, int layer)
{
    maxlayer = max(maxlayer, layer);
    if (node[index].size() == 0)
    {
        Layer[layer]++;
        return;
    }
    for (int i = 0; i < node[index].size(); i++)
    {
        DFS(node[index][i], layer + 1);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int id, k;
        scanf("%d%d", &id, &k);
        while (k--)
        {
            int x;
            scanf("%d", &x);
            node[id].push_back(x);
        }
    }
    DFS(1,1);
    for (int i = 1; i <= maxlayer; i++)
    {
        printf("%d", Layer[i]);
        if (i != maxlayer)printf(" ");
    }
    return 0;
}

BFS:注意maxlayer更新的位置,bfs都在q.pop()之后操作,不要在循环里操作

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 110;
struct node {
    int layer;
    vector<int>child;
}Node[maxn];
int Layer[maxn];
int n, m;
int maxlayer = 0;
void BFS(int root)
{
    queue<int>q;
    Node[root].layer = 1;
    q.push(root);
    while (!q.empty())
    {
        int top = q.front();
        q.pop();
        maxlayer = max(maxlayer, Node[top].layer);
        if (Node[top].child.size())
        {
            for (int i = 0; i < Node[top].child.size(); i++)
            {
                int child = Node[top].child[i];
                Node[child].layer = Node[top].layer + 1;
                q.push(child);
            }
        }
        else Layer[Node[top].layer]++;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int id, k;
        scanf("%d%d", &id, &k);
        while (k--)
        {
            int x;
            scanf("%d", &x);
            Node[id].child.push_back(x);
        }
    }
    BFS(1);
    for (int i = 1; i <= maxlayer; i++)
    {
        printf("%d", Layer[i]);
        if (i != maxlayer)printf(" ");
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 13,158评论 0赞 33
  • 1、通过CocoaPods安装项目名称项目信息 AFNetworking网络请求组件 FMDB本地数据库组件 SD...
    阳明AI阅读 16,468评论 3赞 119
  • 第三章 神秘的房子 默罕默德在市卫长米修斯的带领下,朝着城南角方向走去。 他们一前一后,大约走了十分钟,在一个小平...
    沁水弦歌阅读 552评论 0赞 0
  • 群处守住嘴,独处守住心 悠 然:『文创沙龙』 群处守住嘴: 在和别人相处的时候,一定要注意自己的语言。有的...
    作者悠然阅读 708评论 3赞 5

友情链接更多精彩内容