1 Тема от artem611

  • artem611
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-12-02
  • Сообщений: 2

Тема: Поиск мостов в неориентированном графе

Помогите разобраться с алогритмом. Я еще только учусь кодить. С++ толком не знаю(больше на яве учусь).

const int MAXN = ...;
vector<int> g[MAXN];
bool used[MAXN];
int timer, tin[MAXN], fup[MAXN];
 
void dfs (int v, int p = -1) {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] > tin[v])
                IS_BRIDGE(v,to);
        }
    }
}
 
void find_bridges() {
    timer = 0;
    for (int i=0; i<n; ++i)
        used[i] = false;
    for (int i=0; i<n; ++i)
        if (!used[i])
            dfs (i);
}

Как задается граф vector <int> g[MAXN]? Это что-то вроде матрицы смежности?
Это for (size_t i=0; i<g[v].size(); ++i) я так понимаю, что идем мы по всем смежным вершинам с V?

Ну и получается, что в программе в int main() мне надо будет просто задать наш граф?

Всем заранее спасибо и извиняюсь, если вопрос глуп. Просто я только учусь еще smile

2 Ответ от at1

  • at1
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-06-19
  • Сообщений: 3

Re: Поиск мостов в неориентированном графе

Все, что Вы сказали, по-моему мнению, верно.

Замечания:
vector<int> example; // резиновый массив, изначально нулевого размера.
vector<int> g[MAXN]; // обычный массив "массивов нулевого размера"

Пример чтения графа из файла (часто встречающийся вариант):

int vertices, edges;
scanf("%d%d", &vertices, &edges);
for (int ei = 0; ei < edges; ++ei)
{
  int a, b;
  scanf("%d%d", &a, &b);
  a--, b--;

  // в список смежности вершины "a" добавляем вершину "b".
  // Это соответствует добавлению в конец резинового массива g[a] нового элемента.
  g[a].push_back(b);

  // симметрично для g[b]
  g[b].push_back(a);
}

3 Ответ от artem611

  • artem611
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-12-02
  • Сообщений: 2

Re: Поиск мостов в неориентированном графе

Спасибо за пояснения