班上有N名学生。其中有些人是朋友，有些则不是。他们的友谊具有传递性。如果已知A是B的朋友，B是C的朋友，那么可以认为A也是C的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个N*N的矩阵M，表示班级中学生之间的朋友关系。如果M[i][j]=1，表示已知第i个和j个学生互为朋友关系，否则为不知道。请设计一个算法，输出所有学生中的已知的朋友圈总数。

解题思路：

朋友圈的主要特性是传递性（A→B 是朋友，B→C 是朋友，则 A→C 是朋友），因此可以用到“集合连通性”：

每个学生初始属于一个 “独立集合”（自己是自己的朋友圈）；

若两名学生是朋友（M [i][j]=1），则将他们的集合 “合并”；

最终，每个连通的集合对应一个朋友圈，集合的总数量就是朋友圈总数。

例如：3 名学生中 0 和 1 是朋友、1 和 2 是朋友，合并后 3 人属于同一个集合，对应 1 个朋友圈；若 2 无朋友，则 2 属于独立集合，总朋友圈数为 2。

并查集是专门处理 “集合合并” 和 “元素归属查询” 的数据结构

1. 并查集结构体设计（存储集合状态）

2. 并查集的操作（实现集合管理）

（1）初始化：为每个学生创建独立集合（init 函数）

例如：n=3 时，parent = [0,1,2]，count=3，对应 3 个独立朋友圈。

（2）查找根节点：确定学生的集合归属（find 函数，带路径压缩）

路径压缩：若集合是 “链状”（如 0→1→2→3，3 是根），首次查找 0 的根时，会将 0 直接挂到 3 下（parent[0]=3），后续查找 0 的根只需 1 步，避免重复遍历链状结构，将查找时间复杂度从 O (n) 降为 O (α(n))（α 是阿克曼函数反函数，接近常数）。

（3）合并集合：将朋友的集合合并（unite 函数，按秩合并）

按秩合并：避免合并后集合变成 “长链”（如每次都将高集合挂到矮集合下，会导致高度快速增长），确保集合高度始终较小，进一步优化查找效率。

（4）内存释放：避免内存泄漏（destroy 函数）

动态分配的内存需手动释放，避免程序运行时内存泄漏。

3.遍历关系矩阵，统计朋友圈总数（findCircleNum 函数）

该函数是 “并查集” 与 “问题场景” 的桥梁，通过遍历朋友关系矩阵，调用并查集操作完成朋友圈计数：

遍历优化：只处理上三角矩阵：

朋友关系是双向的（M [i][j]=1 等价于 M [j][i]=1），若遍历整个矩阵（i 从 0 到 n-1，j 从 0 到 n-1），会重复处理(i,j)和(j,i)，导致无效的合并操作。只处理j=i+1的上三角，既覆盖所有朋友关系，又避免重复。

4.main 函数负责 “接收用户输入→调用核心逻辑→输出结果”，并支持多次测试（输入 N=0 退出）：

（1）循环输入学生数量 N：若 N=0，退出程序；否则继续；

（2）动态创建关系矩阵：分配 N×N 的二维数组，存储用户输入的朋友关系；

（3）输入关系矩阵：用户按行输入 N 个数字（0 或 1），表示学生间的朋友关系；

（4）计算并输出结果：调用findCircleNum得到朋友圈总数，打印结果；

（5）释放矩阵内存：避免动态分配的二维数组导致内存泄漏。

5.以 “3 名学生，0 和 1 是朋友，1 和 2 是朋友” 为例，完整流程如下：

（1）用户输入 N=3，输入关系矩阵[[1,1,0],[1,1,1],[0,1,1]]；

（2）findCircleNum初始化并查集：parent=[0,1,2]，count=3；

（3）遍历矩阵上三角：

i=0，j=1：M [0][1]=1，合并 0 和 1 的集合→parent=[1,1,2]，count=2；

i=0，j=2：M [0][2]=0，不操作；

i=1，j=2：M [1][2]=1，合并 1 和 2 的集合→parent=[1,2,2]，count=1；

（4）返回count=1，输出 “朋友圈总数为: 1”；

（5）释放矩阵和并查集内存，等待下一次输入（或输入 N=0 退出）。

C++代码如下：

#include<iostream>
using namespace std;
//并查集结构体
struct UnionFind
{
    int *parent;  //存储每个元素的父节点
    int *rank;    //存储树的秩，用于优化合并
    int count;    //连通分量的数量
    int size;     //元素总数
};
//定义结构体指针类型
typedef struct UnionFind *Tree; 
//初始化函数-创建并初始化UnionFind结构
Tree init(int n);
//查找根节点，带路径压缩
int find(Tree T,int x);
//合并两个集合，按秩合并
void unite(Tree T,int x,int y);
//释放内存
void destroy(Tree T);
//计算朋友圈数量
int findCircleNum(int **M, int n);
int main()
{
    int i,j,N;
    while(1)
    {
	    cout<<"请输入学生数量N: ";
	    cin>>N;
	    if(N==0)
	    {
	    	cout<<"当学生数量N为0时，退出程序！"<<endl;
			break;
		}
	    //动态分配N*N的二维数组
	    int **M=new int*[N];
	    for(i=0;i<N;i++)
	    {
	        M[i]=new int[N];
	    }
	    //输入关系矩阵
	    cout<<"请输入"<<N<<"*"<<N<<"的关系矩阵(每行"<<N<< "个数字，用空格分隔):"<<endl;
	    for(i=0;i<N;i++)
	    {
	        for(j=0;j<N;j++)
	        {
	            cin>>M[i][j];
	        }
	    }
	    //计算并输出结果
	    cout<<"朋友圈总数为: "<<findCircleNum(M,N)<<endl;
	    //释放动态分配的内存
	    for(i=0;i<N;i++)
	    {
	        delete[] M[i];
	    }
	    delete[] M;
	}
    return 0;
}
//初始化函数-创建并初始化UnionFind结构
Tree init(int n)
{
	int i;
    Tree T=new UnionFind;  //分配内存并返回指针
    T->size=n;
    T->count=n;
    T->parent=new int[n];
    T->rank=new int[n];
    for(i=0;i<n;i++)
    {
        T->parent[i]=i;  //初始时每个元素的父节点是自己
        T->rank[i]=0;    //初始秩为0
    }
    return T;  //返回初始化好的指针
}
//查找根节点，带路径压缩
int find(Tree T,int x)
{
    if(T->parent[x]!=x)
    {
        T->parent[x]=find(T,T->parent[x]);  //递归压缩路径
    }
    return T->parent[x];
}
//合并两个集合，按秩合并
void unite(Tree T,int x,int y)
{
    int rootX=find(T, x);
    int rootY=find(T, y);
    if(rootX==rootY)
    {
		return;  //已在同一集合中
    }
    //按秩合并
    if(T->rank[rootX]<T->rank[rootY])
    {
        T->parent[rootX]=rootY;
    }
    else
    {
        T->parent[rootY]=rootX;
        if(T->rank[rootX]==T->rank[rootY])
        {
            T->rank[rootX]++;
        }
    }
    T->count--;  //合并后连通分量减少1
}
//释放内存
void destroy(Tree T)
{
    delete[] T->parent;
    delete[] T->rank;
    delete T;  //释放结构体本身
}
//计算朋友圈数量
int findCircleNum(int **M, int n)
{
    Tree T=init(n);  //初始化并查集  
    //遍历矩阵处理朋友关系
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)  //只处理上三角，避免重复
        {
            if(M[i][j]==1)
            {
                unite(T,i,j);
            }
        }
    }
    int result=T->count;
    destroy(T);  //释放内存
    return result;
}

Python代码如下：

class UnionFind:
    """并查集类，实现初始化、查找(带路径压缩)和合并(按秩合并)操作"""
    
    def __init__(self, n):
        """初始化并查集"""
        self.size = n  # 元素总数
        self.count = n  # 连通分量的数量
        self.parent = list(range(n))  # 存储每个元素的父节点
        self.rank = [0] * n  # 存储树的秩，用于优化合并
    
    def find(self, x):
        """查找根节点，带路径压缩"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 递归压缩路径
        return self.parent[x]
    
    def unite(self, x, y):
        """合并两个集合，按秩合并"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return  # 已在同一集合中，无需合并
        
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        
        self.count -= 1  # 合并后连通分量减少1


def find_circle_num(M, n):
    """计算朋友圈数量"""
    uf = UnionFind(n)  # 初始化并查集
    
    # 遍历矩阵处理朋友关系
    for i in range(n):
        for j in range(i + 1, n):  # 只处理上三角，避免重复
            if M[i][j] == 1:
                uf.unite(i, j)
    
    return uf.count


def main():
    while True:
        try:
            print("请输入学生数量N: ", end="")
            N = int(input())
            
            if N == 0:
                print("当学生数量N为0时，退出程序！")
                break
            
            # 输入关系矩阵
            print(f"请输入{N}*{N}的关系矩阵(每行{N}个数字，用空格分隔):")
            M = []
            for i in range(N):
                row = list(map(int, input().split()))
                # 验证输入的行是否有正确数量的元素
                if len(row) != N:
                    print(f"错误：每行必须输入{N}个数字！")
                    # 清除已输入的行，重新开始输入
                    M = []
                    i = -1  # 因为循环会i+1，所以设为-1让下一次循环从0开始
                    continue
                M.append(row)
            
            # 计算并输出结果
            print(f"朋友圈总数为: {find_circle_num(M, N)}")
            
        except ValueError:
            print("输入错误，请输入有效的整数！")
        except Exception as e:
            print(f"发生错误: {str(e)}")


if __name__ == "__main__":
    main()

Java代码如下：

import java.util.Scanner;

// 并查集类
class UnionFind {
    private int[] parent;  // 存储每个元素的父节点
    private int[] rank;    // 存储树的秩，用于优化合并
    private int count;     // 连通分量的数量
    private int size;      // 元素总数

    // 初始化并查集
    public UnionFind(int n) {
        size = n;
        count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始时每个元素的父节点是自己
            rank[i] = 0;    // 初始秩为0
        }
    }

    // 查找根节点，带路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩路径
        }
        return parent[x];
    }

    // 合并两个集合，按秩合并
    public void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return;  // 已在同一集合中
        }
        
        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
        
        count--;  // 合并后连通分量减少1
    }

    // 获取连通分量数量
    public int getCount() {
        return count;
    }
}

public class FriendCircle {
    // 计算朋友圈数量
    public static int findCircleNum(int[][] M, int n) {
        UnionFind uf = new UnionFind(n);  // 初始化并查集
        
        // 遍历矩阵处理朋友关系
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // 只处理上三角，避免重复
                if (M[i][j] == 1) {
                    uf.unite(i, j);
                }
            }
        }
        
        return uf.getCount();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            System.out.print("请输入学生数量N: ");
            int N = scanner.nextInt();
            
            if (N == 0) {
                System.out.println("当学生数量N为0时，退出程序！");
                break;
            }
            
            // 输入关系矩阵
            System.out.println("请输入" + N + "*" + N + "的关系矩阵(每行" + N + "个数字，用空格分隔):");
            int[][] M = new int[N][N];
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    M[i][j] = scanner.nextInt();
                }
            }
            
            // 计算并输出结果
            System.out.println("朋友圈总数为: " + findCircleNum(M, N));
        }
        
        scanner.close();
    }
}
    

程序运行截图展示：