这题怎么写啊？

常规
1

朋友圈

提交(Submit)

中文 切换语言(Change Language)

时间限制：0.1s 空间限制：128M

题目描述：

班上有 n 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 n*n 的矩阵 M，表示班级中学生之间的朋友关系。如果 M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

输入格式：

第一行是整数 n；(1≤n≤200)

接下来的 n 行，每行 n 个数字，第 i 行第 j 列的数字表示 i 与 j 的朋友关系，1 表示朋友，0 表示未知。

输出格式：

输出一个数字，表示朋友圈总数。

样例输入 ：

3
1 1 0
1 1 1
0 1 1

样例输出 ：

1

4 个赞
2

老师说是并查集

4 个赞
3

考虑对于每个 M_{i,j}=0 的情况合并 i,j 所在集合。

最后看有几个集合即可。具体集合个数是 father_i =i 的 i 的 个数。

4 个赞
4

那能不能用数组模拟呢？

3 个赞
5

你要模拟什么，

4 个赞
6

模拟并查集，但WA20：

#include<bits/stdc++.h>
using namespace std;
int vis[205];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
    	int a,b,c;
    	cin>>a>>b>>c;
    	if(c==1&&vis[a]!=1&&vis[b]!=1){
    		ans++;
    		vis[a]=vis[b]=1;
		}
	}
	cout<<ans;
}
3 个赞
7

这个模拟好像不对

3 个赞
8

你这显然不能这么搞啊。

4 个赞
9

他是要你求集合个数不是合并次数。

4 个赞
10

我知道啊，但我不会并查集…… :sob:

3 个赞
11

大佬求教

3 个赞
12

或许你需要看看这个

3 个赞
13

还有一些并查集的好题
1.纯例题
2.好题

3 个赞
14

还有一些并查集的好题
3.变了个形
4.我到现在都没做出来

3 个赞