Найти ошибку в коде?

Question

[Rushpil]

Задача: В первой строке вводится число N - номера связанных точек(т.е. из любой одной точки можно попасть в любую другую от 0 до N-1). Далее программа получает на вход порцию данных,каждая порция находится в отдельной строке.Первая порция-доступна сразу. А каждая следующая будет доступна тогда,когда наша программа выведет 'WAIT' или 'ATTACK' и выполнит flush. В каждой порции данных первым передается число R-количество пар(связей между вершинами).После него через пробел идут пары чисел, связи между точками(пары означают,что точки между собой связаны).После получения каждой порции данных надо вывести 'WAIT' -если пути от 0 до 9999 точки нету и продолжать ввод порций данных или "ATTACK"-если путь существует,после "ATTACK" программа завершает работу. Подскажите,что не так в моей программе ? Буду рад любому совету.Возможно поиск связи между точками можно осуществить по алгоритму DSU(метод не пересекающихся множеств), но у меня не получилось.

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)

Comments

[Ivan Yakushenko]

Так а что с программой не так?
Или вы думаете сейчас все побегут запускать и дебажить ваш код?

[Rushpil]

Ivan Yakushenko, при первом запуске все нормально:принимается N, принимается порция чисел на 2 проходе выводит ошибку:'int' object has no attribute 'append' ,я подозреваю,что ошибка в вызове func, перед stdout.flush()

[Ivan Yakushenko]

Rushpil, ну так напишите это с подробным трейсбеком в вопросе, мне то вы это зачем пишите?

Answer 1

[longclaps]

Возможно поиск связи между точками можно осуществить по алгоритму 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

Подучите питон - он у вас пока ниже плинтуса. И да - как успехи в предыдущей задаче?

Comments

[Rushpil]

все получилось,спасибо огромное вам и wataru за помощь,без вас бы я не справился,а что насчет моего питона,вы правы,поскольку я только разбираюсь в динамическом программировании и языке в целом.

[longclaps]

Вот это что такое?

for i in range(1,b):
    k.append([int(i-1),int(i)])

Какого типа значение i? Какого типа значения возвращает range? И зачем из int делать int?
Rushpil, тут не до высоких материй, у вас просто грязный код. Аккуратнее надо.

[Rushpil]

longclaps мне все понятно в вашей программе,но опять же я затрудняюсь в этом моменте for pairs in data:
У нас происходит ввод сначала N, на следующей строке первая порция данных. Затем следует проверка,существует ли путь между двумя точками. Если нет то 'WAIT' ,если да ,то "ATTACK' . И только потом вводим следующую порцию данных,а в вашей программе получается,что все порции данных вводятся сразу. Вот я и не могу понять как сделать рекурсию после ввода первой порции,чтобы в data добавлялись новые данные и осуществлялась проверка, если путь нашелся то прекращать проверку. Извините, конечно, за мою глупость,но язык я познаю самостоятельно и кроме как людей,разбирающихся в этом,таких как вы, мне спросить некого.

[Rushpil]

longclaps, я создаю список,в котором 0 вершина связана с 1, 1 со 2 и т.д.,чтобы получилась "сопля",т.е. линейно связанные точки.

[longclaps]

Rushpil,

как сделать рекурсию

Не нужна здесь рекурсия, здесь нужна итерация

while True: # вместо for pairs in data:
    l = list(map(int, input().split()))
    for a, b in zip(l[1::2], l[2::2]): # вместо for a, b in pairs:
          ...............

[tsarevfs]

Rushpil, Обратите внимание, что данное решение может заботать медленно, за O(n^2)
Существует достаточно проятая в реализации ранговая эвристика, которая позволяет добиться практически линейного времени на любых данных.
Разница с наивным подходом в том, что мы будем хранить дополнительный массив рангов, которы позволит нам всегда сливать меньше множество с большим, а не наоборот. Это значит на каждой итерации будет обновлено меньше элементов в массиве.
Так же я советую вынести операции get и union в отдельные функции, а не сливать все в одну портянку.

[longclaps]

Достаточно проятая, говоришь ) Да таких эвристик десятки! И это я не все еще придумал.

Так же, tsarevfs, я советую в учебных задачах реализовывать кампактный код, а не шинковать его на бессмысленные чанки. Под компактным я понимаю умещающийся на один экран. Как у меня )

Спасибо за замечания.

[longclaps]

Обратите внимание, что данное решение может заботать медленно, за O(n^2)

tsarevfs, что-то я вчера подрасслабился и пропустил эту глупость. Смотрим в вашу вики:

Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.

Херня это. Нет, братцы, для каждого элемента списка будем хранить указатель на представителя и всё. Я на массиве (прости, python's list) работаю. Мне такое счастье от того, что у меня ноды не разрежены, а стоят плотно на 0..N, и дурной навигации по списку, которую надо при каждом слиянии перестраивать, у меня нет. И у нас всё вдруг становится линейным (почти).

[tsarevfs]

longclaps, согласен что нет смысла реализовывать это на списках. По второй ссылке с эвристикой код использует массивы.

[Rushpil]

longclaps, Простите пожалуйста еще раз за то,что я надоедаю вам. Объясните пожалуйста,допустим я подставляю свои значения в блок date

data = (
    ((4, 6),),
    ((3, 9),),
    ((9999, 7),),
    ((11, 12), (9, 10)),
    ((8, 10),),
    ((1, 2), (2, 7))
)

,даже не зацикливая. Почему в блоке

def chain_root(a):
    res = []
    while a != root[a]:
        res.append(a)
        a = root[a]
    return res, a

происходит

list index out of range

,если мы берем пары чисел ?

[longclaps]

Rushpil, что-то я не вижу, чему у вас равен N.

[Rushpil]

longclaps, N=9999

[longclaps]

Rushpil, отложите нахер свои штудии и займитесь питоном. Учебников овердохера.
Какой максимальный индекс у списка длины N?

[Rushpil]

longclaps, N-1

[longclaps]

Rushpil, ну так чтож вы туда это суёте

((9999, 7),),

[Rushpil]

longclaps, еще раз спасибо,что объясняете такому глупому,как я

Answer 2

[aRegius]

Подскажите,что не так в моей программе ?

Проверьте на предмет переопределения переменной k вот в этом месте:
for k, v in ribsDict.items()