把“转发到自己所在的所有群,再由群内每个人继续转发到其所有群”的过程,抽象为连通性问题:若两个人出现在同一个群中,他们之间就存在一条无向“连边”,消息会在同一连通分量内传播,最终能收到消息的人就是与首发者处于同一连通分量的所有人。
适用算法:并查集(Disjoint Set Union, DSU/Union-Find) 对于每个群,把群内所有成员两两连通(等价于把该群中的所有人并到同一集合中),最后输出首发者所在集合的大小即可。
核心实现:
starter 与群数 m。在通讯软件中,在群里面转发消息可以使得一条消息扩散到很多人那里。假设已知有 m 个群,其中一个人把一条消息发到他自己所在的所有群里面,这些群里面的每个人又把消息再次转发到他所有的群里面,请问所有群的所有人都转发过一次后,最后几个人收到该消息(包括发消息的人)?输出收到消息的人数(以十进制整数输出,不需要加换行符)。