学校有N个学生，许多同学在学习中与生活中成为了朋友，据说朋友关系有自反性（自己和自己是朋友），有对称性（你和我是朋友，我和你一定也是朋友），还有传递性，即如果A和B是朋友，且B和C是朋友，则A和C也是朋友，于是就形成了许多的朋友圈。下列矩阵表示的四个人的朋友圈：i行 j列为1表示是直接的朋友关系，为0表示并非直接的朋友关系，是否是间接的朋友不清楚。输入样例中，0,1,2是一个朋友圈，3号自己是一个朋友圈。故共有2个朋友圈。请编写程序，根据给定的关系矩阵，计算学校的朋友圈数量。 注意：因为关系矩阵是对称的，故只录入了下三角的数据，也就是只描述了i号学生与其前边的学生的朋友关系，后边的关系未再复述（包括对角线上的自己：N个学生，仅输入了N*(N+1)/2个数据）。

输入样例：

1
2
3
4
5
4
1
1 1
1 0 1
0 0 0 1

输出样例：

输出全校学生中的朋友圈的数量（指没有交集的朋友圈）：

1
2

思路

这道题考察了并查集。并查集的模板主要包括四个部分：初始化，寻找根节点，合并，求连通分量个数。（给大家强烈推荐一篇文章，解释并查集非常形象易懂和有趣，链接）

1. 初始化

1
2
3
4
5
void init() {
	for(int i = 1; i <= 10005; i++) {
		father[i] = i;
	}
}

2. 寻找根节点
一般写法

1
2
3
4
int find(int x) {
	if(father[x] == x) return x;
	return find(father[x]);
}

优化写法（路径压缩）

1
2
3
4
int find(int x) {
	if(father[x] == x) return x;
	return father[x] = find(father[x]);
}

3. 合并集合

1
2
3
4
void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx != fy) father[fx] = fy;
}

4. 连通分量个数

1
2
3
4
5
6
7
int count() {
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(father[i] == i) cnt++;
	}
	return cnt;
}

计算连通分量的个数即为朋友圈的数量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int fa[10005];
void init(int n) {
	for(int i = 0; i < n; i++) {
		fa[i] = i;
	}
}
int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx != fy) fa[fx] = fy;
}
int main() {
	int n;
	cin >> n;
	init(n);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < i+1; j++) {
			int t;
			cin >> t;
			if(t) merge(i, j);
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(fa[i] == i) cnt++;
	}
	cout << cnt;
}