7-11 朋友圈的数量 (10分)

悠悠 2023-01-10 14:35 126阅读 0赞

很简单的一道并查集问题

#include <iostream>
    #include <set>
    using namespace std;
    int fa[10005];
    void init() {
        
    	for(int i = 0; i < 10005; i++) {
        
    		fa[i] = i;
    	}
    }
    int find(int x) {
        
    	if(fa[x] == x) return x;
    	else 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();
    	for(int i = 1; i <= n; i++) {
        
    		for(int j = 1; j <= i; j++) {
        
    			int t;
    			cin >> t;
    			if(t) merge(i, j);
    		}
    	}
    	int cnt = 0;
    	for(int i = 1; i <= n; i++) {
        
    		if(fa[i] == i) cnt++;
    	}
    	cout << cnt;
    }

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

**输入样例：**

4
    1
    1 1
    1 0 1
    0 0 0 1

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