A6269. 新闻传播
编程题
普及-
知识点
题目描述
在某个社交网络中，有 $n$ 个用户被分在 $m$ 个好友群中进行交流。
如果两个用户至少同时出现在一个好友群中，我们就认为他们之间是好友关系。
现在有一条新闻开始在这个社交网络中传播：
- 一开始，只有某个用户 $x$ 知道这条新闻；
- 每一轮中，已经知道新闻的用户会把新闻转发给自己的好友；
- 新知道新闻的好友，在之后的轮次中继续转发给他们的好友；
- 这个过程一直持续，直到不存在这样一对好友：其中一人知道新闻而另一人还不知道。
对于每个用户 $x$（$1 \le x \le n$），我们都假设“最开始只有用户 $x$ 知道新闻”，并按上述规则进行传播。
你需要分别计算：最终会有多少用户知道这条新闻。
如果两个用户至少同时出现在一个好友群中，我们就认为他们之间是好友关系。
现在有一条新闻开始在这个社交网络中传播：
- 一开始，只有某个用户 $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. $$
接下来有 $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$ 知道这条新闻，最终会有多少用户知道这条新闻。
相邻两个整数之间用一个空格隔开。
其中第 $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
说明/提示
### 样例解释 #1
共有 $7$ 个用户、$5$ 个群：
- 群 $1$：$\{2,5,4\}$
- 群 $2$：空
- 群 $3$：$\{1,2\}$
- 群 $4$：$\{1\}$
- 群 $5$：$\{6,7\}$
根据“同群即好友”的规则，可以得到以下几个互不相交的好友圈：
- $\{1,2,4,5\}$ 在若干群中彼此相连；
- $\{3\}$ 单独一个人，没有好友；
- $\{6,7\}$ 两个人在同一个群。
## 数据范围与说明
- $1 \le n, m \le 5 \cdot 10^5$；
- $0 \le k_i \le n$；
- 所有群中用户编号总数之和不超过 $5 \cdot 10^5$；
- 同一群内用户编号互不相同。
共有 $7$ 个用户、$5$ 个群：
- 群 $1$：$\{2,5,4\}$
- 群 $2$：空
- 群 $3$：$\{1,2\}$
- 群 $4$：$\{1\}$
- 群 $5$：$\{6,7\}$
根据“同群即好友”的规则，可以得到以下几个互不相交的好友圈：
- $\{1,2,4,5\}$ 在若干群中彼此相连；
- $\{3\}$ 单独一个人，没有好友；
- $\{6,7\}$ 两个人在同一个群。
## 数据范围与说明
- $1 \le n, m \le 5 \cdot 10^5$；
- $0 \le k_i \le n$；
- 所有群中用户编号总数之和不超过 $5 \cdot 10^5$；
- 同一群内用户编号互不相同。