Number of Provinces

Q: Какова временная сложность задачи Number of Provinces?

O(n²) при поиске в графе или использовании структуры непересекающихся множеств, поскольку оба метода считывают каждую запись матрицы n × n один раз. Структура непересекающихся множеств добавляет множитель α(n) — обратную функцию Аккермана, которая на практике не превышает 4. Дополнительная память — O(n).

Q: Что использовать для задачи «Количество провинций»: DFS, BFS или систему непересекающихся множеств?

Все три возвращают одно и то же количество за время O(n²). DFS или BFS проще всего написать. Union-find — лучший инструмент, когда нужно также отвечать на множество вопросов вида «относятся ли эти два города к одной провинции», поскольку на каждый ответ требуется почти постоянное время.

Q: Чем задача «Количество провинций» отличается от задачи «Количество островов»?

Оба алгоритма подсчитывают связные компоненты. В задаче Number of Islands граф представляет собой сетку, у каждого квадрата не более четырёх соседей, а объём работы составляет O(rows × cols). Здесь граф задан матрицей смежности: любой город может быть связан с любым другим, а для перечисления соседей одного города нужно прочитать целую строку из n элементов.

СреднеСистема непересекающихся множеств Графы

+10

Есть n городов, пронумерованных от 0 до n-1. isConnected[i][j] равно 1, если дорога напрямую соединяет город i и город j, и 0 в противном случае. Дороги работают в обоих направлениях, поэтому матрица симметрична, и каждый город соединён сам с собой.

Провинция — это группа городов, в которой каждый город может добраться до любого другого напрямую или через другие города и из которой не ведёт ни одной дороги наружу. Верните количество провинций.

Функция

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: матрица n × n, 1 там, где дорога напрямую соединяет два города
Возвращаетinteger: количество провинций

Ограничения

1 ≤ n ≤ 150, где n = isConnected.length
isConnected[i].length = n
isConnected[i][j] равно 0 или 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Примеры

Ввод: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Вывод: 2
Пояснение: Город 0 соединён дорогой с городом 3, а город 1 — дорогой с городом 2. Дороги не соединяют эти две пары, поэтому здесь 2 провинции.

Дополнительный вопрос

Каждая дорога теперь открывается в определенный день. Можешь найти первый день, когда все города будут принадлежать одной провинции?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Матрица описывает неориентированный граф: города — это узлы, а каждая 1 — ребро. Провинция — это связная компонента, и 0 между двумя городами не разделяет их, если третий город связывает их обоих. Поиск из каждого непосещённого города или структура непересекающихся множеств для каждого ребра подсчитывает компоненты за O(n²).

Поиск в глубину из каждого непосещённого города

Идея

Непомеченный город не может принадлежать уже посчитанной провинции, потому что каждый поиск помечает всю свою провинцию. Значит, начинается новая провинция. Поиск проходит по строкам матрицы: во втором примере поиск из города 0 достигает города 1, а строка города 1 затем приводит к городу 2, хотя в строке 0 для города 2 стоит 0.

Каждый город извлекается из стека один раз, и для него считывается строка из n элементов, поэтому матрица считывается один раз: время O(n²). Метки и стек содержат не более n городов, поэтому дополнительные затраты памяти составляют O(n).

Алгоритм

Создай флаг посещения для каждого города и установи счётчик в 0.
Просмотри города по порядку и пропускай уже посещённые.
Для ещё не посещённого города увеличь счётчик на 1, отметь его и помести в стек.
Пока в стеке есть города, извлекай один и помещай в стек каждый город из его строки, у которого значение равно 1 и который ещё не посещён, отмечая его при помещении.
Верни счётчик.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

Система непересекающихся множеств со сжатием путей и объединением по рангу

Идея

Начните с n провинций, по одной на каждый город. Каждая единица выше главной диагонали означает, что два города принадлежат одной группе: если их группы различаются, объедините их и уменьшите счётчик на единицу. Во втором примере счётчик начинается с 5, (0, 1) объединяет города 0 и 1, (1, 2) присоединяет город 2 к их группе, и остаётся 3 провинции.

Структура данных Union-find хранит каждую группу в виде дерева: parent[c] указывает на родителя на один уровень выше, а два города принадлежат одной группе, если find проходит по их путям до одного и того же корня. Если ничего не делать, при объединении может образоваться длинный путь, по которому каждый вызов find будет проходить за O(n) шагов. Объединение по рангу помещает более короткое дерево под более высокое, поэтому длина любого пути не превышает log n. Сжатие путей направляет каждый город, встреченный вызовом find, напрямую к корню. Вместе эти методы обеспечивают амортизированную сложность O(α(n)) для каждого вызова find, а на практике α(n) не превышает 4.

Алгоритм

Установите parent[c] = c и rank[c] = 0 для каждого города, а счётчик установите в n.
Для каждой пары i < j, для которой isConnected[i][j] = 1, найдите корни i и j.
В find поднимитесь до корня, затем пройдите по пути ещё раз и укажите корень для каждого города на этом пути.
Если корни различаются, присоедините корень с меньшим рангом к другому, при равных рангах увеличьте ранг на 1 и уменьшите счётчик на 1.
Верните счётчик.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

Ловушки и крайние случаи

Учитывать только прямые дороги. Между городами 0 и 2 во втором примере стоит 0, но они всё равно принадлежат одной провинции.
Считать единицы и делить результат на два. Если три города соединены друг с другом, между ними три дороги и одна провинция.
В системе непересекающихся множеств уменьшать счётчик при каждой 1, а не только тогда, когда корни двух множеств различаются.
Сравнивать parent[i] и parent[j]. У двух городов из одной группы могут быть разные родители, если один находится глубже; сравнивай find(i) и find(j).
Присоединять сам город j, как в parent[j] = find(i). Если j уже входил в группу, остальные города этой группы не будут включены в объединение.

Частые вопросы3

Какова временная сложность задачи Number of Provinces?

O(n²) при поиске в графе или использовании структуры непересекающихся множеств, поскольку оба метода считывают каждую запись матрицы n × n один раз. Структура непересекающихся множеств добавляет множитель α(n) — обратную функцию Аккермана, которая на практике не превышает 4. Дополнительная память — O(n).

Что использовать для задачи «Количество провинций»: DFS, BFS или систему непересекающихся множеств?

Все три возвращают одно и то же количество за время O(n²). DFS или BFS проще всего написать. Union-find — лучший инструмент, когда нужно также отвечать на множество вопросов вида «относятся ли эти два города к одной провинции», поскольку на каждый ответ требуется почти постоянное время.

Чем задача «Количество провинций» отличается от задачи «Количество островов»?

Оба алгоритма подсчитывают связные компоненты. В задаче Number of Islands граф представляет собой сетку, у каждого квадрата не более четырёх соседей, а объём работы составляет O(rows × cols). Здесь граф задан матрицей смежности: любой город может быть связан с любым другим, а для перечисления соседей одного города нужно прочитать целую строку из n элементов.

def findCircleNum(isConnected):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Ожидаемый вывод