Количество провинций

Средняя

medium , graph , disjoint_set

05 February 2025

Описание задачи #

Есть n городов, некоторые из которых соединены между собой.

Если город a напрямую соединен c городом b, а город b напрямую соединен с городом c, тогда города a и c косвенно соединены между собой.

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

Вам дана матрица isConnected размером n x n, где isConnected[i][j] = 1, если i-й город и j-й город напрямую соединены, и isConnected[i][j] = 0 в противном случае.

Верните общее количество провинций.

Ограничения #

Размер матрицы n — это целое число в диапазоне от 1 до 200
В качестве значений в матрице используются только 1 b 0
isConnected[i][j] == isConnected[j][i]

Примеры #

Входные данные

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

Ответ: 2

Входные данные

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

Ответ: 3

Решение #

У этой задачи достаточно много решений и все они достаточно сложные. Но мы можем легко решить задачу, если знать как работает структура данных DisjointSet (также известная как UnionFind).

Подробно про реализацию структуры данных DisjointSet можно посмотреть в этом посте.

Как только мы имеем реализованную структуру данных, задача становится крайне легкой.

Алгоритм решения:

Создать инстанс структуры данных DisjointSet.
Определить переменную numberOfProvinces равную n в начале состояния. Далее мы будем уменьшать ее значение при объединении городов в провинцию.
Так как главная диагональ матрицы isConnected отображает соединение каждого города с самим собой, то мы можем ее не рассматривать. Также нам не требуется проверять всю матрицу так как isConnected[i][j] == isConnected[j][i], поэтому будем перебирать элементы над главной диагональю. Для этого запустим цикл в цикле по i и j от i = 0 и j = i + 1.
Если два города соединены (isConnected[i][j] == 1) и они уже не находятся в одном множестве, то мы объединяем эти города в множество при помощи метода — то мы объединяем города i и j в одну провинцию.

В итоге после перебора элементов матрицы переменная numberOfProvinces будет показывать количество получившихся провинций.

Реализация #

package number_of_provinces

type DisjointSet struct {
	nodes []int
}

func NewDisjointSet(size int) DisjointSet {
	nodes := make([]int, size)

	for i := 0; i < size; i++ {
		nodes[i] = i
	}

	return DisjointSet{
		nodes: nodes,
	}
}

func (uf *DisjointSet) find(node int) int {
	return uf.nodes[node]
}

func (uf *DisjointSet) union(x int, y int) {
	rootX := uf.find(x)
	rootY := uf.find(y)

	if rootY != rootX {
		for i := range uf.nodes {
			if uf.nodes[i] == rootY {
				uf.nodes[i] = rootX
			}
		}
	}
}

func findCircleNum(isConnected [][]int) int {
	n := len(isConnected)
	disjointSet := NewDisjointSet(n)

	numberOfProvinces := n

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if isConnected[i][j] == 1 && disjointSet.find(i) != disjointSet.find(j) {
				numberOfProvinces -= 1
				disjointSet.union(i, j)
			}
		}
	}

	return numberOfProvinces
}

class DisjointSet {
    readonly nodes: number[];

    constructor(size: number) {
        this.nodes = new Array(size);

        for (let i = 0; i < size; i++) {
            this.nodes[i] = i;
        }
    }

    find(node: number): number {
        return this.nodes[node];
    }

    union(x: number, y: number): void {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX !== rootY) {
            for (let i = 0; i < this.nodes.length; i++) {
                if (this.nodes[i] === rootY) {
                    this.nodes[i] = rootX;
                }
            }
        }
    }
}

export const findCircleNum = (isConnected: number[][]): number => {
    const n = isConnected.length;
    const disjointSet = new DisjointSet(n);

    let numberOfProvinces = n;

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1 && disjointSet.find(i) != disjointSet.find(j)) {
                numberOfProvinces -= 1;
                disjointSet.union(i, j);
            }
        }
    }

    return numberOfProvinces
}

Оценка сложности #

По времени

Перебор матрицы занимает O(n²)
Поиск методом find занимает O(n)
Объединение методом union занимает O(n)

Общая сложность по памяти O(n²).

По памяти

Сложность O(n) для хранения состояния структуры DisjointSet.

Оригинал задачи на Leetcode

Algorithmics