# LeetCode: 1267. 统计参与通信的服务器¶

## 1、题目描述¶

输入：grid = [[1,0],[0,1]]



输入：grid = [[1,0],[1,1]]



输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]



• m == grid.length
• n == grid[i].length
• 1 <= m <= 250
• 1 <= n <= 250
• grid[i][j] == 0 or 1

## 2、解题思路¶

• 使用并查集
• 将每个元素与这一行第一个1还有这一列第一个1放到同一个集合中
class DFU:
def __init__(self, length):
self.data = list(range(length))
self.size = [1] * length

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
if self.size[xp] > self.size[yp]:
self.size[xp] += self.size[yp]
self.data[yp] = xp
else:
self.size[yp] += self.size[xp]
self.data[xp] = yp

def get_size(self, x):
return self.size[x]

def count_nums_more_than_one(self):
res = 0
for index, i in enumerate(self.data):
if index == i and self.size[index] > 1:
res += self.size[index]
return res

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def countServers(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])

d = DFU(row * col)
row_first = [-1] * row
col_first = [-1] * col

for x in range(row):
for y in range(col):
cur = x * col + y
if grid[x][y]:
if row_first[x] == -1:
row_first[x] = cur
if col_first[y] == -1:
col_first[y] = cur

for x in range(row):
for y in range(col):
cur = x * col + y
if grid[x][y]:
if row_first[x] != -1:
d.union(cur, row_first[x])
if col_first[y] != -1:
d.union(cur, col_first[y])

return d.count_nums_more_than_one()

• 实际上也可以直接利用当前行与当前列的和进行判断
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
row_sum = [sum(r) for r in grid]
col_sum = [sum([grid[i][j] for i in range(row)]) for j in range(col)]

appear_once = 0
for i in range(row):
for j in range(col):
if grid[i][j] and row_sum[i] == 1 and col_sum[j] == 1:
appear_once += 1
return sum(row_sum) - appear_once