问题：给定一个m*m的二维矩阵，m表示信号接收点的个数。矩阵由0和1组成，如果对应的位置为1，则表示两点相连。至少需要多少个信号发射器才能保证所有点都连通？可以接收信号，例如：[[1.,0.,1.,0.,0.],[0.,1.,0.,1.,0.],[1.,0.,1.,0.,0.],[0.,1.,0.,1.,1.],[0.,0.,0.,1.,1.]]位置0和2相连，1、3、4与其他不相连，所以至少需要对信号发射机进行2次分析：这道题其实就是求解独立不相交的组数。我的想法是：找到位置为1的点的坐标例如：[(2,0),(3,1),(4,3)]初始化未分组的点{0,1,2,3,4}从第一个元素中找到可以合并的组，并且从不从中删除组。重复3，直到所有元素合并分组，完成分组+独立点个数之和，即最小个数defget_nin_count(arr):deff(related_nodes):"""在第一组的基础上，扫描可以与其合并的组"""target=related_nodes[0]remain=[]forginrelated_nodes[1:]:#如果有交集就合并，否则放入要分组的setiftarget&g:target|=gelse:remain.append(g)returntarget,remainm=len(arr)groups,remain_nodes=[],set(range(m))#查找关联点remain=[]foriinrange(m):forjinrange(i):ifarr[i][j]==1:remain.append({i,j})#直到所有whileremain:print(remain)g,remain=f(remain)groups.append(g)remain_nodes-=greturnlen(groups)+len(remain_nodes)测试一下arr1=[[1,0,1,0,0],[0,1,0,1,0],[1,0,1,0,0],[0,1,0,1,1],[0,0,0,1,1]]get_min_count(arr1)#2
