众所周知，头条笔试面试都非常注重对数据结构和算法的考察。今天笔试还蛮沮丧的，准确来说是有点可惜，两道 AC，两道40%，最后一题想出 idea 的时候时间已经所剩无几，已经来不及编码测试和提交，好在考试结束后坚持把 idea 实现出来了。题目描述如下：

N 个人，M 对关系，(A,B) 表示 A 用户关注了 B，关注也具有传递性，如果 A 关注了 B，B 关注了 C，则间接认为 A 关注了 C，如果一个用户被所有的 N 个用户直接或间接关注，那么这个用户就是抖音红人，要求找出抖音红人总数

input：

3

3

1 2 2 1 2 3

explain：

总人数：3

总关系对儿：3

[1,2,2,1,2,3] =>1 关注 2，2 关注 1，2 关注 3 => 3是抖音红人

initial idea：

用 map 存储，key 表示用户，value 是个数组，表示所有直接关注 key 用户的用户，然后对 map 遍历，对所有关注 key 的用户数组进行遍历，找出所有间接的关注关系，再分别对数组中的每个 key 递归，将结果合并，去重，用一个 visit 数组记录是否访问过。

后来觉得实现起来有点麻烦，也想过 plan2：

先将关系转成邻接矩阵，然后用 DFS 对图进行遍历，所有节点为根分别 DFS，找出满足条件的节点，每次 DFS 后需要对 visit 数组重置，每次 DFS 遍历节点时也需要记录。放弃这个想法的原因是自己图相关的算法写的很少，怕自己实现不出来。

最后想到可以在方案一的基础上进行改进：

  1. 用邻接矩阵存储关系，行和列都从 1 开始存储，第 i 行表示用户 i 关注的人，第 i 列表示所有关注 i 的人，maps[i][j] === 1 表示 i 用户关注 j 用户，等于 0 表示不关注

  2. visit 数组保存是否相加（合并）过

  3. 核心思路：

    对第 i 列进行遍历，找到其中所有 值大于等于1 且 没有被合过 且 非自身关注自身 的节点，比如 maps[k][i] 第 k 行满足条件，则将第 k 列和当前列（第 i 列）合并，合并的意思是相应位置相加，结果保存在当前列中， 然后 visit[i][j] = 1 设置已合并的标记，重复上述过程，直到找不到符合条件的节点为止。从第 1 列到最后一列，重复上述过程。

  4. 对结果二维数组进行遍历并判断：

    除了自身关注自身（i==j）外，仍然存在等于 0 的情况，则说明此人不是抖音红人，反之则是，结果++

  5. JavaScript 二维数组初始化是真的蛋疼！

代码：(JavaScript 实现，没有测试所有 case！)

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
const popular = function(n, m, relations) {
    let maps = [] //邻接矩阵
    let visit = [] //保存是否合并过
    let res = 0
    //初始化邻接矩阵：第 i 行表示 i 关注的人，第 i 列，表示关注 i 的人，从 1 开始存储
    for (let i = 1; i <= n; i++) {
        maps[i] = []
        visit[i] = []
        for (let j = 1; j <= n; j++) {
            maps[i][j] = 0
            visit[i][j] = 0
        }
    }
    for (let i = 0; i < relations.length - 1; i += 2) {
        maps[relations[i]][relations[i + 1]] = 1
    }
    /**
     * 列项合并相加
     */
    for (let j = 1; j <= n; j++) {
        let flag = true
        while (flag) {
            flag = false
            for (let i = 1; i <= n; i++) {
                if (!visit[i][j] && maps[i][j] >= 1 && i !== j) {
                    flag = true
                    //i 列合并到 j 列上
                    visit[i][j] = 1
                    for (let k = 1; k <= n; k++) {
                        maps[k][j] += maps[k][i]
                    }
                    break;
                }
            }
        }
    }
    //判断是否有0
    for (let j = 1; j <= n; j++) {
        let i
        for (i = 1; i <= n; i++) {
            if (maps[i][j] === 0 && i !== j) {
                break;
            }
        }
        if (i > n) {
            res++
        }
    }
    return res
}
console.log(popular(6, 11,
    [1,2,2,3,2,4,3,2,4,1,4,2,4,3,4,5,5,2,5,3,6,5]
))