1 Ответ от artem611

(2 ответов, оставленных в Algo)

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

Перейти к разделу: Algo

2 Тема от artem611

(2 ответов, оставленных в Algo)

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

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

Перейти к разделу: Algo