华为机试C语言-找到比自己强的人数

题目描述：https://pycoder.blog.csdn.net/article/details/127216746?spm=1001.2014.3001.5502
https://blog.csdn.net/qq_27695659/article/details/125882686

这道题一直再想有没有更好的方法，很遗憾，没能想出来。因为相邻的两层递归无法建立联系，当前老师比自己强的人数无法从徒弟的身上找到答案，中间的减枝无法去掉，不清楚是否会超时，时间复杂度还是挺高的。供大家参考吧，有更好的解法欢迎大家赐教~

#include 
#include 
#include 
#include 

int dfs(int map[100][2], int size, int target, int teacher, int cnt) {
    for (int i = 0; i < size; i++) {
        if (map[i][0] == teacher) {
            if (map[i][1] < target) {
                cnt++;
            }
            cnt += dfs(map, size, target, map[i][1], 0);
        }
    }

    return cnt;
}

int main(void) {
    char str[1000] = {0};
    int row = 0, col = 0;
    int index = 0;
    int map[100][2] = {0};
    int max = 0;
    int res[100];

    scanf("%s", str);

    int left, right, len;
    char node[100];
    char* tmp;
    int teacher, student;
    for (int i = 1; i < strlen(str) - 1; i++) {
        if (str[i] == '[') {
            left = i + 1;
        } else if (str[i] == ']') {
            right = i - 1;
            len = right - left + 1;
            strncpy(node, &str[left], len);
            node[len] = '\0';
            printf("%s\n", node);

            tmp = strtok(node, ",");
            teacher = atoi(tmp);
            tmp = strtok(NULL, ",");
            student = atoi(tmp);

            map[index][0] = teacher;
            map[index++][1] = student;
            max = fmax(max, teacher);
            max = fmax(max, student);
        }
    }

    for (int i = 1; i <= max; i++) {
        res[i] = dfs(map, index, i, i, 0);
    }

    printf("[");
    for (int i = 1; i < max; i++) {
        printf("%d,", res[i]);
    }
    printf("%d]\n", res[max]);


    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67