Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Реализация алгоритма определения яркости изображения на языке PHP https://www.cyberforum.ru/ algorithms/ thread1515067.html
Эта тема не вопрос, не просьба помочь. Просто захотелось реализовать на языке PHP алгоритм определения яркости изображений и поделиться данной наработкой на этом замечательном кибер форуме. Может быть услышать какие либо отзывы о скрипте, предложения :) Данный алгоритм это не реализация мирового проверенного академического алгоритма определения яркости изображения. Данный алгоритм придумай и...
Алгоритмы Алгоритм вычисления полинома в n точках
Здравствуйте! Прошу помощи с алгоритмом для вычисления значений полинома в нескольких точках. Мне нужно написать программу, которая будет делать это со скоростью О(n*lg^2n), такой алгоритм описан в Кормене (30-5, второе издание), но я банально не могу его понять, точнее "предложить". Вот что написано в Кормене: Перекопировать текст не было возможности Буду очень благодарен за помощь, кровь...
Алгоритмы Алгоритм суммы листьев дерева Здравствуйте. Есть дерево, в котором известны значения только самых последних листьев (т.е. тех, которые не имеют детей). Значения всех остальных листьев не известны. Подскажите пожалуйста алгоритм, который мог бы рассчитать сумму для всех неизвестных листьев, таким образом, чтобы значения листа было равно сумме значений дочерних листьев. Буду весьма благодарен, если ещё и пример будет на... https://www.cyberforum.ru/ algorithms/ thread1514190.html Алгоритмы Алгоритм выборки ячейки из системы координат квадратом https://www.cyberforum.ru/ algorithms/ thread1513921.html
Доброго времени суток. Пишу сейчас плагин для одной игрушки. Необходимо получать координаты ячейки обходя прежнюю фигуру по периметру, радиус ограничен числом R. Шаг сетки - 1. Так же хочу в любой момент продолжить выполнение алгоритма с последней позиции. Т.е. сохранить/достать переменные. Наверняка моё объяснение ужасно, так что вот знатокам gif'ки для понимания. Работа алгоритма...
Что такое приближенный алгоритм и в чем отличие от эвристического или жадного? Алгоритмы
Правильно ли я понимаю, что приближенный алгоритм - это алгоритм, который всегда дает почти точное решение и его точность доказана, в то время как эвристический - это тоже приближенный, но его точность не доказана и в некоторых случаях могут получаться совершенно не приближенные результаты или даже не оптимальные? В то время как жадный выбирает локально оптимальные решения, и так же может давать...
Алгоритмы Длиннейшая цепочка https://www.cyberforum.ru/ algorithms/ thread1513241.html
Нашел задачу на олимпе: Дан список целых положительных чисел. Найдите размер его максимального подмножества, которое можно выстроить в цепочку таким образом, чтобы среди любых двух соседних элементов один делился на другой. Входные данные Первая строка ввода содержит количество тестов t (1 ≤ t ≤ 35). Каждая из следующих t строк содержит количество элементов множества n (1...
Алгоритмы Алгоритмы для поиска паросочетаний https://www.cyberforum.ru/ algorithms/ thread1512869.html
Всем привет! Собственно вопрос: Какие существуют для поиска паросочетаний алгоритмы, кроме Куна и Венгерского? Применение, например, такое: какой мальчик будет танцевать с девочкой или какая команда с какой будет играть. Всем спасибо!
Как написать генератор 3D карты? Алгоритмы
Не могу придумать как написать генератор 3D кары. Карта представляет собой массив xyz. Каждая ячейка массива хранит в себе 1 элемент карты. На карте должны присутствовать горы не выше определенной высоты, реки, озера, пещеры. Пока есть две идеи: 1)описать поверхность формулой и потом заполнить все точки снизу этой поверхности. Но вот как это сделать я не знаю. Не знаю как описать такую...
Алгоритмы Бинарный поиск по двум упорядоченным масивам https://www.cyberforum.ru/ algorithms/ thread1511657.html
Подозреваю, что очень глупый вопрос. Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой), внутри которых упорядочены по массе. Предлжите способ за 11 взвешиваний найти 1006-ую гирьку по массе среди всех. https://cache-spb05.cdn.yandex.net/download.cdn.yandex.net/shad/exam-2012.pdf Может я тупой, но в качестве решения вижу только слияние групп(массивов) с...
Алгоритмы Месть Ли Чака Попалась задача на e-olimp: http://www.e-olymp.com/ru/problems/88 Нужно определить может ли человек с отметкой 'g' добраться до отметки 'e' так что человек с отметкой 'l' не смог бы поймать 'g'. 'l' не может перейти на участок 'e'. Люди могут двигаться вверх, вниз, вправо, влево или стоять на месте. 1: Я вызываю BFS с точки где находится 'l' и нахожу минимальные расстояния до всех... https://www.cyberforum.ru/ algorithms/ thread1510856.html
Алгоритмы Изменение контрастности изображений
Изменяю контрастность в разных программах и получаю совершенно разный результат. Может быть существуют разные алгоритмы изменения контрастности? Я в Интернете почитал, вроде бы изменить контрастность - ничего сложного и контрастность описывается по простой формуле (А-В)/В. Тем не менее, если сравнивать работу графических редакторов GIMP и PAin_Net - получается совершенно разные результаты. Похоже...
Модератор
Эксперт функциональных языков программирования
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
29.08.2015, 17:56 0

Количество мостов в неориентированном графе - Алгоритмы - Ответ 8021144

29.08.2015, 17:56. Показов 4272. Ответов 2
Метки (Все метки)

Лучший ответ Сообщение было отмечено Disaster7 как решение

Решение

Вы этот алгоритм имели ввиду?
http://www.intuit.ru/studies/c... 019?page=2

Добавлено через 12 минут
Обходом в глубину получаем остовное дерево (если граф многосвязный, то получаем лес деревьев... будем считать, что граф односвязный).
Рёбра графа, попавшие в остовное дерево, называются прямыми, а не попавшие - обратными.
В каждую вершину (кроме корня) ведёт ровно одно прямое ребро. Это ребро будет мостом, если нет другого пути обратно. То есть, если нет обратного ребра, из этой вершины или её потомка ведущего в предшественника этой вершины.

Вернуться к обсуждению:
Количество мостов в неориентированном графе Алгоритмы
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.08.2015, 17:56
Готовые ответы и решения:

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

Поиск цикла заданной длины в неориентированном графе
Всем привет! Есть такая задача: дана система двусторонних дорог. Найти замкнутый путь длиной не...

Алгоритм поиска элементарных циклов в неориентированном графе
Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри...

Найти все циклы в неориентированном графе по матрице смежности
Здравствуйте. Задача в заголовке. С построением матрицы смежности проблем нет, вопрос в алгоритме...

2
29.08.2015, 17:56
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.08.2015, 17:56
Помогаю со студенческими работами здесь

В неориентированном графе посчитать количество компонент связности
2. Компоненты связности В неориентированном графе посчитать количество компонент связности. В...

Посчитать количество компонент связности в неориентированном графе
В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и...

Выбрать минимальное количество вершин в двудольном неориентированном графе
У нас есть двудольный неориентированный граф. Нужно выбрать минимальное количество вершин так,...

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

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru