1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

  • 把“转发到自己所在的所有群,再由群内每个人继续转发到其所有群”的过程,抽象为连通性问题:若两个人出现在同一个群中,他们之间就存在一条无向“连边”,消息会在同一连通分量内传播,最终能收到消息的人就是与首发者处于同一连通分量的所有人。

  • 适用算法:并查集(Disjoint Set Union, DSU/Union-Find) 对于每个群,把群内所有成员两两连通(等价于把该群中的所有人并到同一集合中),最后输出首发者所在集合的大小即可。

  • 核心实现:

    1. 读入首发者姓名 starter 与群数 m。
    2. 逐行读取每个群,以逗号分割成员,去除姓名两端空格,为每个未出现过的姓名分配并查集编号。

P3828.第3题-转发群消息

    1000ms Tried: 61 Accepted: 22 Difficulty: 5 所属公司 : 荣耀
    算法与标签>并查集

题目内容

在通讯软件中,在群里面转发消息可以使得一条消息扩散到很多人那里。假设已知有 mmm 个群,其中一个人把一条消息发到他自己所在的所有群里面,这些群里面的每个人又把消息再次转发到他所有的群里面,请问所有群的所有人都转发过一次后,最后几个人收到该消息(包括发消息的人)?输出收到消息的人数(以十进制整数输出,不需要加换行符)。

输入描述

发第一条消息的人名

群组个数 mmm

群组 111 成员人名列表

群组 222 成员人名列表

...

群组 mmm 成员人名列表

人名是英文字符串,包含英文字母和空格,最大长度不超过 100100100 字符。

群组个数 mmm 是十进制整数,最大不超过 100100100 。

群组成员人名列表包含 111 至多个人名,两个人名之间以逗号分隔。

输出描述

以十进制输出最后能收到消息的人数。

包括第一个发消息的人也统计进去,重复接收到消息只统计一次。

样例1

输入

Jack
3
Jack,Tom,Anny,Lucy
Tom,Danny
Jack,Lily

输出

6

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 0, 52ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?