AcWing 3587. 连通图---python实现
原题链接
简单
作者:
wcyyyooo
,
2022-07-07 01:19:11
,
所有人可见
,
阅读 230
查并集
时间复杂度 $O(n^2)$
def find(x):
if p[x] != x:
return find(p[x])
return x
while True:
try:
n, m = map(int, input().split(' '))
p = [i for i in range(n + 1)]
cnt = [1 for i in range(n + 1)]
for i in range(m):
a, b = map(int, input().split(' '))
x = find(a)
y = find(b)
if x != y:
p[x] = y
cnt[y] += cnt[x]
if cnt[find(1)] == n:
print("YES")
else:
print("NO")
except EOFError:
break
图的遍历 (dfs)
时间复杂度 $O(n^2)$
g = [[0 for i in range(1010)] for j in range(1010)]
st = [False for i in range(1010)]
n, m = 0, 0
def dfs(root):
if st[root]:
return
st[root] = True
for i in range(1, n + 1):
if g[root][i]:
dfs(i)
while True:
try:
n, m = map(int, input().split(' '))
for i in range(m):
a, b = map(int, input().split(' '))
g[a][b] = 1
g[b][a] = 1
st = [False for i in range(1010)]
dfs(1)
flag = True
for i in range(1, n + 1):
if not st[i]:
flag = False
break
if not flag:
print("NO")
else:
print("YES")
for i in range(n + 1):
for j in range(n + 1):
g[i][j] = 0
except EOFError:
break