Нужен алгоритм поиска в графе вершины из которой достижимы все вершины.
(BFS по каждой вершине не предлагать).

Делаешь DFS от любой вершины, запоминая для каждой из низ время, когда ты из неё выходишь
После чего проверяешь(есче DFS) вершину с самым большим временем выхода. ИМХО заработает

судя по всему граф ориентированный.
алгоритм за О(n^3) устроит?

Цитата(eskaflone @ 18.11.2005, 20:57)

алгоритм за О(n^3) устроит?

Ну наверное ты предложишь DFS или BFS от каждой вершины, ну или модернизацию этого. А то, что я предложил работает за O(E + V), т.е в худшем случае (если граф представлен в виде матрици) за O(n*n)

1)время выхода это количество посещенных вершин?
2)DFS от любой вершины или от всех?

опиши алгоритм подробнее.
ЗЫ
DFS - поиск в глубину?

Цитата(yaja @ 16.11.2005, 21:10)

Делаешь DFS от любой вершины, запоминая для каждой из низ время, когда ты из неё выходишь После чего проверяешь(есче DFS) вершину с самым большим временем выхода. ИМХО заработает

может быть приведете док-во, а то фраза имхо заработает, лишает надежд.

Есть такой умный метод.
Находишь все компоненты сильной связности графа Г.
Далее строишь граф Г1 у которого:
! вершинам соответствуют компоненты сильной связности графа Г.
! ребро (а, в) означает, что из соответствующей компоненты сильной связности а можно попасть в компоненту в.
Если Г1 связный и у него одна вершина Y, в которую не входит ни одно ребро, то задача имеет решение. Ответом будут все вершины компоненты сильной связности, которая соотвествовала вершине Y.
Умный метод. Но легче ничего не нашлось.

Код

void DFS() {   for (int i = 1; i <= n; i++) {      color[i] = WHITE     way[i] = 0;   }   time = 1;      for (int i = 1; i <= n; i++) {     if (color[i] == WHITE) {       dfs(i);     }   } } void dfs(int u) { // поиск в глубину   color[u] = GRAY;   for (для всех смежных с u вершин v) {     if (color[v] == WHITE) dfs(v);   }   way[time++] = u; // запоминаем последовательность посещения вершин   // или leave[u] = time++; это то, что я имел ввиду время выхода   // запоминать way - лучше, т.к. иначе в нем придется находить максимальный элемен, что стоит времени } // return номер вершины от которой достижимы все int find() {   DFS();   int u = way[n]; // если в графе и есть вершина от которой достижимы все, то это несомненно эта   // проверим, достижимы ли остальный вершины от этой   for (int i = 1; i <= n; i++) {      color[i] = WHITE   }   time = 1;   dfs(u);   for (int i = 1; i<= n; i++)      if (color[i] == WHITE) return -1; // нет требуемой вершины   retrun u; }

Заметим, что если из а - достижимы все вершины, то и из любой в, из которой достижима а, будут достижимы все вершины графа. Тогда из свойств dfs'а и из некоторых интуитивных соображений следует, что проверять надо только последнюю вершину. Я не знаю как точно это описать, но рассуждения как в топологической сортировке графа


poor_yorik Твой метод будет работать только на неориентированном графе (а насколько я понял граф ориентированный, иначе можно было бы только один раз запустить dfs) На ориентированном графе он работать не будет. Вот пример(граф задан списком ребер: первая вершина - начало ребра)
0 1
1 2
В нем три компоненты сильной связности, поэтому твой метод выдаст, что требуемой вершины не существует, а на самом деле такая вершина сушествует - 0 вершина

Это сообщение отредактировал(а) yaja - 20.11.2005, 23:37