N=int(input())
b=N+1
k=[]
for i in range(1,b):
k.append([int(i-1),int(i)])
def func(k):
p=list(map(int,input().split()))
for i in range(2,len(p),2):
k.append([p[i-1],p[i]])
ribsDict = dict() #Заводим словарь
for i in range(10000): #Пробегаем по всем вершинам
connectRibs = [] #заводим список
for j in range(len(k)):#Проходим по всем ребрам
if k[j][0] == i + 1:#Проверяем граф на связность,ищем,
connectRibs.append(k[j][1])#с какой вершиной связана каждая из вершин
elif k[j][1] == i + 1:#
connectRibs.append(k[j][0])#
ribsDict[i + 1] = connectRibs
z=[]
for k, v in ribsDict.items():
z.append(v)
visited = [False] * 10000
component = [-1] * 10000 # для каждой вершины храним номер её компоненты
num_components = 0
def dfs(v):
component[v] = num_components
visited[v] = True
for w in z[v]:
if visited[w] == False:
dfs(w)
visited = [False] * 10000
for v in range(10000):
if not visited[v]:
dfs(v)
num_components += 1
w=9999
v=0
if component[v]==component[w]:
print('ATTACK')
else:
print('WAIT')
func(k)
stdout.flush()
func(k)
Возможно поиск связи между точками можно осуществить по алгоритму DSU(метод не пересекающихся множеств), но у меня не получилось.
N = 5
data = (
((0, 1),),
((1, 2), (3, 2)),
((4, 3),),
((1, 3), (4, 2))
)
root = list(range(N))
def chain_root(a):
res = []
while a != root[a]:
res.append(a)
a = root[a]
return res, a
for pairs in data:
for a, b in pairs:
aa, ra = chain_root(a)
bb, rb = chain_root(b)
if ra > rb:
ra, rb = rb, ra
for node in [*aa, *bb, rb]:
root[node] = ra
aa, ra = chain_root(N - 1)
if ra:
for node in aa:
root[node] = ra
print('WAIT')
else:
print('ATTACK')
break
Простой
Средний
