2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示 在节点网络中，只有当 gr

2023-06-10：给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示

在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，

且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。

这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，

并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。

如果有多个节点满足条件，返回索引 最小的节点 。

initial 中每个整数都不同。

输出：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]。

输入：0。

答案2023-06-10：

主要思路如下：

1.建立并查集，将感染恶意软件的节点标记出来。

2.遍历节点连接，如果两个节点都没有被感染，则在并查集中合并这两个节点。

3.对于initial中的每个节点，遍历其能够直接连接的节点，如果节点未被感染，则将其在并查集中的祖先标记为initial中的该节点，如果该祖先已被标记为其他initial中的节点，则将其标记为-2。

4.统计在同一个initial的所有节点中，连接的总节点数，找出连接数最多的initial节点。

5.返回最小索引的节点。

时间复杂度为$O(n^2)$，其中n是节点数，因为要对每个节点进行遍历和合并操作，最坏情况下需要$O(n^2)$次遍历和合并操作。

空间复杂度为O(n)，其中n是节点数，因为需要使用一个并查集数组来存储节点的父节点，另外还需要使用一个数组来记录每个节点是否被感染和每个initial节点的连接数量。这些数据占用的空间都是O(n)的。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述