c语言小白求解一道算法题，能编写运行出结果立即采纳给分

Question

这是一道C语言算法测试题，题目有点长，但看着图片和例子，耐心多读一下就能很容易理解，同学都说题目不难，但本人实在是小白，特此求助，能编写运行出正确结果则采纳给分，拜托了。同学说这道题要用 动态数组malloc创建。

一个网络由M个城市和M-1条连接它们的道路组成的。城市在 [0 …（M-1) ]范围内用不同的整数标记。

如下图，道路以这样的方式连接城市，每对不同的城市通过道路组成的路径连接。只有一种方法可以从任何城市到达任何其它城市。必须经过的“直接道路”的数量被称为这两个城市之间的距离。

例如，考虑以下由十个城市和九条道路组成的网络：

城市2和4直接相连，因此它们之间的距离是1.城市4和7通过由“直接道路” 4-0, 0-9和 9-7组成的路径连接; 因此它们之间的距离为3。

其中一个城市是首都，此题目标是计算在距离首都 1,2,3，...，M-1的每个距离处的城市的数量。

如图，如果数字1是首都，那么离首都不同距离的城市将如下：

9处于距离1;
0,3,7处于距离2;
8,4在距离3;
2，5，6距离为4。

假设给出以下声明：

struct Results {

int ＊ A;
int N.
};
（A代表需要返回的数组，N代表数组的大小）
要求写一个函数

struct Results solution（int T [ ]，int M），

给定由M个整数组成的非空的零索引数组T（描述M个城市和M-1条道路组成的网络），返回由M-1个整数组成的数组（表示距离首都1,2，…，M-1的每个距离处的城市数目）。

数组T描述了一个城市网络，如下所示：

如果T [P] = Q且P = Q，则P是首都;
如果T [P] = Q且 P不等于Q，则P和Q之间存在“直接道路”

例如，给定以下由十个元素组成的数组T; （请详细看此例）

T [0] = 9 T [1] = 1 T [2] = 4
T [3] = 9 T [4] = 0 T [5] = 4
T [6] = 8 T [7] = 9 T [8] = 0
T [9] = 1

因为 T [1] = 1且1=1，则此时1为首都，
则该函数应返回[1，3，2，3，0，0，0，0，0]，如上所述。

假设：
M是在范围[1 ... 100,000]内的整数;
数组T的每个元素是在范围[0 ... M-1]内的整数;
在任何两个不同的城市之间只有一个（可能是间接的）连接。

复杂度：

预期最坏情况时间复杂度为O（M）;
预期的最坏情况空间复杂度为O（M），超出输入存储（不计算输入参数所需的存储）。

输入数组的元素可以修改。

Answer 1

我看是对的！

struct Results solution(int T[],int M)
{
    int cap = 0;
    int* res = (int*)malloc((M-1)*sizeof(int));
    for(int i=0;i<M-1;i++)
    {
        res[i] = 0;
    }
    for(int i=0;i<M;i++)
    {
        int v = T[i];
        int n = i;

        int index = 0;
        if(n == v)
        {
            continue;
        }
        while(v != n)
        {
            index++;
            n = v;
            v = T[v];
        }

        res[index-1]++;
    }

    Results* rs = (Results *)malloc(sizeof(Results));
    rs->A = res;
    rs->N = M-1;

    return *rs;
}