← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6269 | 新闻传播

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

在某个社交网络中，有 $n$ 个用户被分在 $m$ 个好友群中进行交流。
如果两个用户至少同时出现在一个好友群中，我们就认为他们之间是好友关系。

现在有一条新闻开始在这个社交网络中传播：

  • 一开始，只有某个用户 $x$ 知道这条新闻；
  • 每一轮中，已经知道新闻的用户会把新闻转发给自己的好友；
  • 新知道新闻的好友，在之后的轮次中继续转发给他们的好友；
  • 这个过程一直持续，直到不存在这样一对好友：其中一人知道新闻而另一人还不知道。
对于每个用户 $x$（$1 \le x \le n$），我们都假设“最开始只有用户 $x$ 知道新闻”，并按上述规则进行传播。
你需要分别计算：最终会有多少用户知道这条新闻。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5 \cdot 10^5$），分别表示用户数和好友群数。

接下来有 $m$ 行，第 $i$ 行描述第 $i$ 个好友群：

  • 首先是一个整数 $k_i$（$0 \le k_i \le n$），表示该群中的用户数量；
  • 接下来有 $k_i$ 个互不相同的整数，表示属于该群的用户编号（编号范围为 $1 \sim n$）。
保证
$$ \sum_{i=1}^{m} k_i \le 5 \cdot 10^5. $$

输出格式

输出一行，包含 $n$ 个整数。
其中第 $i$ 个整数表示：如果一开始只有用户 $i$ 知道这条新闻，最终会有多少用户知道这条新闻。

相邻两个整数之间用一个空格隔开。

输入输出样例

输入 #1
7 5
3 2 5 4
0
2 1 2
1 1
2 6 7
输出 #1
4 4 1 4 4 2 2
C++ 编辑器
输入
输出