Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
mikelll
16 / 16 / 6
Регистрация: 27.12.2010
Сообщений: 163
1

Поиск вершины с максимальной степенью в двудольном графе

25.02.2018, 12:15. Просмотров 813. Ответов 4
Метки нет (Все метки)

Здравствуйте, имеется двудольный граф (X, Y).
X - это пары целых чисел [a, b]
Y - это просто целые числа: k
и [a, b] смежно k <=> a <= k <= b
Нужно найти вершину из Y с максимальной степенью (если их несколько то первую). В X вершин мало, но в Y очень много, и простой перебор не работает. Как быть?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2018, 12:15
Ответы с готовыми решениями:

поиск цикла максимальной длинны в графе
Никто не подскажет как в неориентированном графе можно найти цикл максимальной...

Алгоритм, вычисляющий по матрице смежности вершину с максимальной степенью
Помогите, плиз, составить алгоритм для вычисления вершины с максимальной...

Как найти степень вершины в ориентированом графе?
Как найти степень вершины в ориентированом графе?

Реализовать алгоритм А* для поиска оптимального пути из начальной вершины в конечную на графе
Привет Нужно реализовать этот алгоритм для поиска оптимального пути из...

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и...

4
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,409
25.02.2018, 14:41 2
Цитата Сообщение от mikelll Посмотреть сообщение
В X вершин мало, но в Y очень много, и простой перебор не работает.
Все вершины из Y придётся перебрать в любом случае. Или Вы чего-то не договариваете?
0
mikelll
16 / 16 / 6
Регистрация: 27.12.2010
Сообщений: 163
25.02.2018, 15:56  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
Все вершины из Y придётся перебрать в любом случае. Или Вы чего-то не договариваете?
Видимо что-то недоговариваю: изначально задача формулируется так:
Есть n - отрезков [a, b], 0 <= a < b <= 1000000000, 0 < n < 1000, некоторые из них пересекаются, нужно найти первую точку в которой пересекаются наибольшее число отрезков
0
salam
181 / 162 / 29
Регистрация: 10.07.2012
Сообщений: 774
25.02.2018, 16:14 4
вам всего лишь нужно найти точку, в которой пересекается наибольшее число отрезков. при числе отрезков до 1000 это делается очень просто за квадрат поддержанием левой и правой границы пересечения.
просто на всякий случай скажу, что при больших количествах отрезков решается методом сканирующей прямой.
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,409
25.02.2018, 19:30 5
Лучший ответ Сообщение было отмечено mikelll как решение

Решение

По-моему, можно за logn отсортировать (отдельно) левые и правые границы отрезков, а затем пройтись по ним, добавляя количество за левые границы и вычитая за правые.
Как-то так:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solve(a):
    al = sorted(map(lambda x: x[0], a))
    ar = sorted(map(lambda x: x[1], a))
    i, j = 1, 0
    max_x, max_cnt, cnt = al[0], 1, 1
    while True:
        while i < len(al) and al[i] <= ar[j]:
            cnt += 1
            i += 1
        if cnt > max_cnt:
            max_x, max_cnt = al[i-1], cnt
        if i >= len(al):
            return (max_x, max_cnt)
        while ar[j] < al[i]:
            cnt -= 1
            j += 1
(На нормальном языке всё это можно было бы в 3 строчки записать)

Добавлено через 32 минуты
Функциональный вариант кода:
Python
1
2
3
def solve(a):
    points = sorted((y for x in a for y in [(x[0],1),(x[1],-1)]), key=lambda x: (x[0],-x[1]))
    return min(accumulate(points, lambda x,y: (y[0],x[1]+y[1])), key=lambda x: (-x[1],x[0]))[0]
1
25.02.2018, 19:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.02.2018, 19:30

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru