Вопрос: Как оптимизировать (ускорить) код на python?

Лучший ответ: 1. Используй array вместо списков там, где можно. Иногда выгодней использовать множества. Особенно если ожидаются частые if X in C
2. Используй генераторы вместо списков там, где возможно
3. Убери весь говнокод вроде:if w != []:def listmerge(lstlst):
    all=[]
    for lst in lstlst:
      all.extend(lst)
    return allwhile [] in loc:
4. Да вообще-то, тут всё говнокод. Лучше убери всё.

Худший ответ: Первая ошибка - не использовать внятные имена переменных, в итоге в коде и логике совершенно невозможно разобраться. Проще заново переписать. Во-вторых, никогда не занимайтесь поиском x in list - для этого есть set'ы. В-третьих, не используйте индексы для итерации по списку, именно для этого придумали enumerate(). Вот предварительный рефакторинг:def user_input():
    # n, m = int(input()), int(input())
    n = 2
    m = 4
    # a = [[int(i) for i in 'input()'.split()] for w in range(m)]
    first = [[1, 2], [3, 4, 5], [6, 7], [8, 9, 10, 11]]
    # input()
    # b = [int(i) for i in input().split()]
    second = [2, 3]
    return first, second, n

def process(list_of_lists, n):
    # Можно ли использовать множества? А вместо вложенных списков - tuple или set.
    seen_lists, seen_numbers = [], []
    has_at_least_two_items = lambda lst: lst and len(lst) >= 2
    for sublist in filter(has_at_least_two_items, list_of_lists):
        number0, number1 = sublist[:2]
        numbers = {number0, number1}  # Для ускорения проверок <x in Y>
        # Ни одно из чисел не встречалось ранее
        if not numbers.issubset(seen_numbers):
            seen_lists.append(sublist)
            seen_numbers.extend(sublist)
            # Здесь бы вставить continue и уменьшить вложенность блока ниже, но зачистка seen_lists перед return мешает
        else:  # Обработка списка, напоминающая сортировку пузырьком
            # Почему перебор до конца списка, а не до seen_lists[:-1]? Поправил.
            for i, seen_list_i in enumerate(seen_lists[:-1]):  # Заметка: слайс возвращает КОПИЮ списка
                sl_i = set(seen_list_i)  # Для ускорения проверок <x in Y>
                common = len(numbers.intersection(seen_numbers))
                # Оба числа встречались раньше
                if common == 2:
                    if numbers.issubset(sl_i):
                        continue
                    # Что будет, когда i == j == len(seen_lists) - 1?
                    for j, seen_list_j in enumerate(seen_lists[i:], i):  # Заметка: слайс возвращает КОПИЮ списка
                        sl_j = set(seen_list_j)  # Для ускорения проверок <x in Y>
                        if (number0 in sl_i and number1 in sl_j) or (number1 in sl_i and number0 in sl_j):
                            seen_list_i.extend(seen_list_j)
                            seen_list_j.clear()
                # Раньше встречалось только одно число из двух
                elif common == 1:
                    # Дальше у одного числа приоритет перед другим;
                    # Нельзя ли сделать nx = numbers - sl_i? Но проверить, что nx - это одно число, а не {number1, n2}
                    if number0 in sl_i:
                        nx = number1
                    elif number1 in sl_i:
                        nx = number0
                    else:
                        continue
                    seen_list_i.append(nx)
                    seen_numbers.append(nx)
        # Эта зачистка точно на своём месте? Можно её сделать перед return? Или удалять пустые сразу (выше)?
        seen_lists = [sublist for sublist in seen_lists if sublist]
    # В чём смысл этого результата?
    return len(seen_lists) - len(seen_numbers) + n

def main(first, second, n):
    for value in second:
        first[value-1].clear()  # В чём смысл?
        print(process(first, n), end=' ')


if __name__ == '__main__':

    main(*user_input())