Помогите с задачей с++ или питон на графы

Question

Помогите с задачей с++ или питон на графы

Рейтинг: 0Ответов: 3Опубликовано: 02.08.2023

Постройте какой-нибудь неориентированный граф из N вершин содержащий K компонент связности.

пример

ввод

5 2

вывод

Входные данные Даны два числа N и K, записанных в одной строке(оба меньше ста).

Выходные данные Выведите матрицу смежности этого графа (она должна быть симметричной относительно главной диагонали, на главной диагонали должны стоять нули).

Скажите пожалуйста как это вообще решать, тут никаких ДФС, БФС я не вижу(просто текстом или кодом)

python c# графы

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

В полном графе из N вершин N(N - 1)/2 рёбер. Соберём рёбра в список и случайно его перемешаем.

Заведём граф без ребёр и будем добавлять в него рёбра из списка по одному. После каждого добавления будем подсчитывать число компонент связности. Оно не возрастает, уменьшается с шагом единица. Рано или поздно получим K компонент. В этот момент запомним индекс ребра i. Продолжим пока не станет K - 1 компонента. Запомним индекс j. Случайно выберем число ребёр из [i, j). Построим матрицу используя это число рёбер. Задача решена.

Этим способом может быть сгенерирован любой возможный граф из N вершин с K компонентами связности.

Сложность O(N²) если для подсчёта компонент связности воспользоваться системой непересекающихся множеств. Код ниже реализует эту программу:

import random


def components(n, edges):
    parent = list(range(n))
    rank = [0] * n

    def find_set(i):
        if parent[i] != i:
            parent[i] = find_set(parent[i])
        return parent[i]

    def connect(i, j):
        assert i != j
        assert parent[i] == i
        assert parent[j] == j

        if rank[i] > rank[j]:
            parent[j] = i
        else:
            parent[i] = j
            if rank[i] == rank[j]:
                rank[i] += 1

    yield 0
    for k, (i, j) in enumerate(edges, start=1):
        i = find_set(i)
        j = find_set(j)
        if i != j:
            connect(i, j)
            yield k
    yield len(edges)


def print_matrix(n, edges):
    m = [[0] * n for _ in range(n)]
    for i, j in edges:
        m[i][j] = 1
        m[j][i] = 1

    for row in m:
        print(*row)


def main():
    n, k = map(int, input().split())
    edges = [(i,  j) for j in range(n) for i in range(j)]
    random.shuffle(edges)

    it = components(n, edges)
    for _ in range(n - k):
        next(it)
    i = next(it)
    j = next(it)

    print_matrix(n, edges[:random.randrange(i, j)])


main()

P.S. Давно мечтал применить disjoint-set-union. Вот получилось.

Answer 2

▲ 3

"Любой" граф сгенерировать нетрудно - разделить вершины на K групп, в каждой группе обеспечить связность, соединив вершины в цепочку, и набросав ещё сколько то ребер для вершин из этой группы.

Для того, чтобы граф был менее скучным, вершины перед делением на группы можно перемешать случайным образом.

Answer 3

▲ 3

Вот, не мучаясь (идея из комментария):

int n, k;
cin >> n >> k;
for(int i = 0; i < n; ++i)
{
    for(int j = 0; j < n; ++j)
        cout << (i >= k-1 && j >= k-1 && i != j) << " ";
    cout << "\n";
}

Проверку n >= k допишите самостоятельно...

Помогите с задачей с++ или питон на графы

Ответы