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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 07.12.2007, 21:08
Михаил

 
Сообщений: n/a

мосты и точки сочленения
объясните мне алгоритм поиска мостов и точек сочленения, НЕ использующий кучу
  #2  
Старый 07.12.2007, 22:07
гость

 
Сообщений: n/a

Причем тут куча? Мосты в графе находятся модифицированным поиском в глубину. Пара вспомогательных массивов - это максимум что тебе для этого потребуется.
  #3  
Старый 08.12.2007, 03:20
Пользователь

Отправить личное сообщение для M_Gustokashin Посмотреть профиль Найти все сообщения от M_Gustokashin
 
Регистрация: 24.09.2006
Адрес: Москва, Багратионовская
Сообщений: 81

визуализатор 1: http://rain.ifmo.ru/cat/view.php/vis...l/bridges-2001
визуализатор 2: http://rain.ifmo.ru/cat/view.php/vis...omponents-2005
книжка:
http://www.olympiads.ru/books/mskoly...ormatolymp.pdf (стр. 218-236)
  #4  
Старый 09.12.2007, 20:38
Михаил

 
Сообщений: n/a

поиск мостов
2Гость: я знаю, что модифицированный поиск в глубину. далее как? в чём модификация?
2M_Gustokashin: книжка не открывается(нет доступа к ...), а визуализаторы уже смотрел до этого. не помогли
  #5  
Старый 10.12.2007, 01:57
гость

 
Сообщений: n/a

Модификация следующая - во-первых потребуется хранить для каждой вершины время ее обнаружения, пусть это будет массив d[x]. Во-вторых, потребуется массив low[x] = минимум из d[x] и значений d[y] среди всех обратных ребер (z, y), таких что z - вершина в поддереве (дерева поиска в глубину) вершины x. Это значение можно вычислять в ходе поиска в глубину, как показано в процедуре ниже. Неформально говоря, low[x] - самая верхняя вершина дерева поиска (точнее d[x] этой вершины), в которую можно попасть из поддерева x с помощью обратного ребра в этом поддереве.

Прямое ребро (x,y) является мостом если и только если low[y]=d[y]. (Обратное ребро никогда не может быть мостом). Вершина x является точкой сочленения если low[x] = d[x], за исключением случая когда она - корень дерева поиска и имеет менее чем двух потомков в дереве.

Примерная реализация:
Код:
int d[MAXN], low[x], counter;

void dfs(int x, int parent) {
  int kids = 0;
  d[x] = low[x] = counter++;
  для каждой вершины y смежной с x {
    if (y != parent) {
      if (d[y] == 0) {
        kids++;
        dfs(y, x);
        if (low[y] == d[y]) {
          // ребро (x,y) - мост
        }
        low[x] = min(low[x], low[y]);
      } else {
        // обратное ребро
        low[x] = min(low[x], d[y]);
      }
    }
  }

  if (d[x] == low[x] && (parent != -1 || kids >= 2)) {
    // вершина x - точка сочленения
  }
}

...

memset(d, 0, sizeof(d));
counter = 1;
for (int x = 0; x < N; x++) if (d[x] == 0) dfs(x, -1);
  #6  
Старый 10.12.2007, 12:48
Михаил

 
Сообщений: n/a

Спасибо
спасибо гостю за объяснение
  #7  
Старый 02.06.2008, 00:54
Новичок

Отправить личное сообщение для nick_9999 Посмотреть профиль Найти все сообщения от nick_9999
 
Регистрация: 02.06.2008
Сообщений: 1

скиньте код всей проги на С
считывающую матрицу ребер из файла
__________________
Nick_9999
  #8  
Старый 13.12.2010, 00:43
Новичок

Отправить личное сообщение для Natalya91 Посмотреть профиль Найти все сообщения от Natalya91
 
Регистрация: 13.12.2010
Сообщений: 1

Не могу сообразить как посчитать у каждой точки сочленения количество блоков, которые она связывает... Чтоб при удалении точки сочленения количество образованных компонент связности было максимальным.. Помогите, пожалуйста
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
точки ilyitch Вычислительная геометрия 1 03.09.2009 15:18
Определение принадлежности точки к 3D объекту fastmod Вычислительная геометрия 2 18.09.2007 13:38
Определение координат точки Nudnik Вычислительная геометрия 2 13.09.2007 20:34
Алгоритм поиска точки Invader Математические алгоритмы 3 26.07.2007 15:41
проверка принадлежности точки многоугольнику hotice Вычислительная геометрия 1 17.01.2007 13:26