字节跳动2020届秋招8月25日，算法第四题
def fun2(a,b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return b
if __name__ == "__main__":
n = int(input())
suger = [int(x) for x in input().strip().split(' ')]
net = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(i+1, n):
if fun2(suger[i], suger[j]) > 1:
net[i][j] = 1
net[j][i] = 1
vis = [0]*n
ans = 0
while min(vis) == 0:
t = [i for i in range(n) if vis[i] == 0]
vis[t[0]] = 1
q = []
q.append(t[0])
res = 0
while q:
h = q.pop(0)
res += 1
for j in range(n):
if net[h][j] == 1 and vis[j] == 0:
q.append(j)
vis[j] = 1
ans = max(ans, res)
print(ans) 通过70%
优化了下 内存
def fun2(a,b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return b
if __name__ == "__main__":
n = int(input())
suger = [int(x) for x in input().strip().split(' ')]
net = []
for i in range(n):
node = []
for j in range(i+1, n):
if fun2(suger[i], suger[j]) > 1:
node.append(j)
net.append(node)
vis = [0]*n
ans = 0
while min(vis) == 0:
t = [i for i in range(n) if vis[i] == 0]
vis[t[0]] = 1
q = []
q.append(t[0])
res = 0
while q:
h = q.pop(0)
res += 1
for j in net[h]:
if vis[j] == 0:
q.append(j)
vis[j] = 1
ans = max(ans, res)
print(ans) 
查看1道真题和解析
