并查集---服务器广播

题目描述
服务器连接方式包括直接相连，间接相连。A和B直接连接，B和C直接连接，则A和C间接连接。直接连接和间接连接都可以发送广播。

给出一个 N * N 数组，代表N个服务器，

matrix[i][j] == 1，则代表 i 和 j 直接连接；不等于1时，代表 i 和 j 不直接连接。
matrix[i][i] == 1, 即自己和自己直接连接。
matrix[i][j] == matrix[j][i]。
计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

输入描述
输入为N行，每行有N个数字，为0或1，由空格分隔，构成N*N的数组，N的范围为 1 <= N <= 40

输出描述
输出一个数字，为需要广播的服务器的数量

用例1
输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3台服务器互不连接，所以需要分别广播这3台服务器

用例2
输入
1 1
1 1
输出
1
说明
2台服务器互相连接，所以只需要广播其中一台服务器

class Union:
    def __init__(self,n):
        # 初始化并查集，创建一个父节点数组 fa
        # 每个元素的父节点初始化为它本身
        self.fa = [i for i in range(n)]
        #记录当前连通组件的数量
        self.count = n

    def find(self,x):
        if x!=self.fa[x]:
            self.fa[x]=self.find(self.fa[x])
            return self.fa[x]
        return x
    def union(self,x,y):
        x_fa = self.find(x)
        y_fa = self.find(y)
        if x_fa!=y_fa:
            self.fa[y_fa] = x_fa
            self.count-=1
arrays=[]
while True:
    try:
        arrays.append(input().split())
    except:
        break
n = len(arrays)
ufs = Union(n)
for i in range(n):
    for j in range(n):
        if arrays[i][j]=='1':
            ufs.union(i,j)
print(ufs.count)

原文地址：https://blog.csdn.net/TTz012/article/details/143889318

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！