Форум программистов, компьютерный форум CyberForum.ru

Максимальное подмножество попарно не связанных друг с другом окружностей - C++

Восстановить пароль Регистрация
 
dev.nikor
 Аватар для dev.nikor
25 / 26 / 1
Регистрация: 26.07.2010
Сообщений: 297
21.04.2013, 19:18     Максимальное подмножество попарно не связанных друг с другом окружностей #1
Здравствуйте, есть вот такая задача: На плоскости задано множество окружностей. Две окружности A и B назовём связанными, если они пересекаются либо существует третья окружность C заданного множества, связанная с A и B. Выбрать максимальное подмножество попарно не связанных друг с другом окружностей.

Сначала я строю что-то типа матрицы смежности, в которой a[i][j]=1, если i-я и j-я окружности связанны, остальные элементы равны нулю.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int** CreateAdjacencyMatrix(std::vector<Circle>& circleCollection) {
    int size = circleCollection.size();
    int** adjMatrix = new int*[size];
    for(int i = 0; i < size; i++) {
        adjMatrix[i] = new int[size];
    }
 
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) {
            //Если окружности пересекаются
            if(CircleCross(circleCollection[i], circleCollection[j])){
                adjMatrix[i][j]=adjMatrix[j][i]=1;
            }else adjMatrix[i][j]=adjMatrix[j][i]=0;
         //Ищем смежную окружность, которая пересекается с 2мя текущими
            for(int k=0; k<size; k++){
                if(k==i||k==j)continue;
 
                if(CircleCross(circleCollection[i],    circleCollection[k])&&CircleCross(circleCollection[j], circleCollection[k]))
                    adjMatrix[i][j]=adjMatrix[j][i]=1;
            }
        }
    }
    return adjMatrix;
}
Вот только дальше я понятия не имею что нужно сделать, что бы найти наибольшее множество несвязанных окружностей. Подскажите пожалуйста, как дальше поступить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 19:18     Максимальное подмножество попарно не связанных друг с другом окружностей
Посмотрите здесь:

Определить попарно номера окружностей, которые имеют хотя бы одну общую точку C++
C++ АТД список. Расположение одинаковых элементов друг за другом
Вывести четыре следующих друг за другом гласных букв C++
Найти максимальное по числу вершин подмножество C++
Файлы и строки: проверить каждую строку на сходство друг с другом C++
C++ Объединить два массива друг за другом
Из заданного множества int чисел определить максимальное подмножество C++
C++ Как правильно потоки должны взаимодействовать друг с другом?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему

Метки
c++
Опции темы

Текущее время: 08:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru