leetcode：547、朋友圈

题目来源

• leetcode

题目描述

题目解析

题意

给出一个二维数组，它一定是个正方形。

• 二维数组的索引可以看成是朋友圈的编号

• 二维数组的值表示关系：1表示认识，0表示不认识

  • M[i][j] = 1：表示i认识j
  • （由题意）M[i][j] = 1，那么M[j][i]也为1，也就是j认识i

• 也就是说：

  • 对角线一定全是1，因为自己是认识自己的
    • M[i][i] = 1
  • 而且这个矩阵是对称的
    • M[i][j] = 1
    • M[i][j] = 1

• 求有几个朋友圈
  

并查集

根据二维数组生成一个并查集

刚开始时，有集合$（1）、（2）、（3）、（4）$

一行行遍历数组

• 刚开始时是第一行：
  • 0和0是认识自己的，之前已经有了$(0)$，不用管
  • 0和1不认识，不用管
  • 0和2认识，因此$(0)$合并$（2）$，得到$（0，2）$
  • 0和3不认识，不用管
  • 0和4认识，因此合并$（4）$，得到$（0，2、4）$
• 然后第二行
  • 1和0不认识
  • 1和1认识，之前已经有了$(1)$，不用管
  • 1和2不认识
  • 1和3认识，合并$（1）、（3）$得到$（1，3）$
  • 1和1不认识
• 然后第三行，对于2
  • 2和0认识：原来应该得到$(2，0)$，这个$(2，0)$已经在第一行中出现过了，所以不用管
• 第四行
  • 3和1认识：$（1）、（3）$之前已经合并了，不用管
• 第五行，得到$(4)$
  • 4和0，$（0）、（4）$之前已经合并了，不用管

也就是说生成了两个集合： $（0，2、4）、（1，3）$，所以朋友圈的个数是2

因为这个矩阵高度对称，所以根据这个集合生成并查集时，只遍历右上角就可以了。

总的来说：

• 先根据N生成集合{0}、{1}、{2}、{3}
• 遍历矩阵的左上角，如果发现M[i][j] == 1，那么就将i和j合并
• 最终返回联通量

为什么要help数组，因为数组的操作比栈快多了