Поиск мостов

Необходимо в заданном графе найти все мосты.
    Мост - ребро графа, при удалении которого увеличивается количество компонентов связности.
    В нашей реализации функция возвращает массив цветов вершин. Если две связанные вершины имеют различный цвет - это мост.
    Асимптотика: если граф задан списком рёбер O(M + N), если матрицей смежности O(N²).

Листинг C++

void dfs_reverse (int &v, vector < vector < >int > > &D,
                  vector < int > &is, vector < int > &c)
{
    is[v] = 1;
    c.push_back (v);

    for (int i = 0; i < D[v].size( ); ++ i)
        if (is[i] == 0 && D[v][i])
        {
            D[v][i] = 0;
            dfs_reverse (i, D, is, c);
        }
}
void dfs_color (int &v, vector < vector < int > > &D,
                vector < int > &col, int &c)
{
    col[v] = c;

    for (int i = 0; i < D[v].size (); ++ i)
        if (col[i] == 0 && D[v][i])
            dfs_color (i, D, col, c);
}
void bridge (vector < vector < int > > D, vector < int > &col)
{
    int i, j;
    int n = D.size ();
    vector < int > is (n, 0);
    vector < int > c;

    // ориентируем наш граф в сторону, из которой идём
    for (i = 0; i < n; ++ i)
        if (is[i] == 0)
            dfs_reverse (i, D, is, c);

    // красим вершины орграфа
    col.assign (n, 0);
    int color = 0;
    for (i = 0; i < c.size (); ++ i)
        if (col[c[i]] == 0)
        {
            ++ color;
            dfs_color (c[i], D, col, color);
        }
}

01.06.2007, 14:57

По всем вопросам обращаться: rumterg@gmail.com