即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

AOJ ALDS1_7_A 树

编程语言 qq_36988616 6℃ 0评论

给你树的一些信息,要你按要求输出树。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 100005
#define INF (1 << 30)
typedef long long ll;
using namespace std;

vector<int> child[N];   //由于子节点个数不确定,vector比较合适
int parent[N];
int GetDepth(int idx)
{
    int ret = 0;
    while (parent[idx] != -1)
    {
        ++ret;
        idx = parent[idx];
    }
    return ret;
}
const char *str[3] = { "root", "internal node", "leaf" };
int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int n;
    scanf("%d", &n);
    fill(parent, parent + n, -1);
    int id, k, c;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &id, &k);
        for (int j = 0; j < k; ++j)
        {
            scanf("%d", &c);
            parent[c] = id;
            child[id].push_back(c);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        int depth = GetDepth(i);
        int status;
        if (depth == 0)
            status = 0;
        else if (child[i].size())
        {
            status = 1;
            sort(child[i].begin(), child[i].end());
        }
        else
            status = 2;
        printf("node %d: parent = %d, depth = %d, %s, ", i, parent[i], depth, str[status]);
        printf("[");
        for (int j = 0; j < child[i].size(); ++j)
        {
            if (j)
                printf(", ");
            printf("%d", child[i][j]);
        }
        printf("]\n");
    }
    return 0;
}

转载请注明:CodingBlog » AOJ ALDS1_7_A 树

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情