作者：远洋箭 | 来源：互联网 | 2023-05-17 09:28
题目描述很简单的问题。有n个人，分成m组，若有一个组中有人的颜值为正无穷，则这个人将会把组里所有人的人的颜值同化为正无穷。n个人的编号分别为0-n-1。若一开始只有0号成员的颜值为正无穷，那么最后颜
题目描述
很简单的问题。有n个人，分成m组，若有一个组中有人的颜值为正无穷，则这个人将会把组里所有人的人的颜值同化为正无穷。n个人的编号分别为0-n-1。若一开始只有0号成员的颜值为正无穷，那么最后颜值为正无穷的成员会有多少个。
输入
多组输入数据，每组数据第一行为两个数n，m。
接下来m行，每行第一个数为小组成员数t，接下来t个数为小组成员的编号。（水题，数据都很小，不用考虑数据大小）
输出
对于每组数据，输出一行，为最后颜值为正无穷的人数。
输入样例
100 3
2 0 1
2 1 2
2 2 3
输出样例
4
算法分析
这道题应该是考察并查集的，但是我用的暴力做法。先设立一个father数组，标记结点i是否和0同组，同组则为0，不同组则为自身。输入m行数据，每行t个数据，所以设立了一个二维数组group，数组每行的第一个元素记录这一行的t值，这样就把所有数据放在二维数组中了。然后遍历数组的每一行，如果这一行有0，就把这一行的所有点的father置为0。遍历结束之后再遍历一遍数组的每一行，如果这一行存在father为0的点，则再把这一行的所有点的father置为0。最后遍历father的每一个点，算出father为0的点的数量输出即可。
参考代码
1 #include
2 using namespace std;
3
4 /*
5 100 3
6 2 0 1
7 2 1 2
8 2 2 3
9 */
10
11 int father[10000];
12
13 int findf(int item) {
14 return father[item]==item?item:father[item]=findf(father[item]);
15 }
16
17 int main() {
18 int n,m;
19 while(~scanf("%d%d",&n,&m)) {
20 for(int i=0;ii;
21 int group[m][1000];
22 for(int i=0;i) {
23 int t;
24 scanf("%d",&t);
25 group[i][0]=t;
26 for(int j=1;j<=t;j++) scanf("%d",&group[i][j]);
27 }
28 for(int i=0;i) {
29 bool zero=false;
30 for(int j=1;j<=group[i][0];j++) {
31 if(group[i][j]==0) zero=true;
32 }
33 if(zero) {
34 for(int j=1;j0];j++) {
35 father[group[i][j]]=0;
36 }
37 }
38 }
39 bool ganran=false;
40 for(int i=0;i) {
41 for(int j=1;j<=group[i][0];j++) {
42 if(father[group[i][j]]==0) {
43 ganran=true;
44 break;
45 }
46 }
47 if(ganran) {
48 for(int j=1;j<=group[i][0];j++) {
49 father[group[i][j]]=0;
50 }
51 }
52 }
53 int cnt=0;
54 for(int i=0;i) {
55 // printf("%d ",father[i]);
56 if(father[i]==0) cnt++;
57 }
58 printf("%d\n",cnt);
59 }
60 }
京公网安备 11010802041100号