Компоненты вершинной двусвязности

Question

Дан неориентированный граф без петель в следующем формате:

Первая строка - n m (|V|, |E| соответственно)
Следующие m строк содержат описание ребер: i u_i v_i.

Требуется выделить компоненты вершинной двусвязности в нем в след. формате:

Первая строка - количество компонент вершинной двусвязности графа
Вторая строка - m чисел, которые говорят, к какой компоненте связности относится i-ое ребро

Тест:

Вход:

Выход:

2
1 1 1 2 2 2

Так вот, вроде бы теория в целом правильная, но на тестах скрытых падает (тест выше код мой проходит)... Теорию черпал из след. источников:

Возможно, проблема в том, что я как-то неправильно работаю с ребрами, но вроде кратность я учитываю. Вот сам код:

#include <iostream>
#include <vector>
#include <map>
#include <set>

#define fast_cin() std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL)

int n, m, T;
std::vector<std::vector<int>> G;
std::vector<bool> used, visited, is_multiple_edge;
std::vector<int> best_up, tin;
std::set<int> art_points;
std::map<int, int> colors;
std::map<std::pair<int, int>, int> edges_ind;

int max_color;

std::pair<int, int> Edge(int a, int b) {
    if (a > b) std::swap(a, b);
    return {a, b};
}

void add_edge(int a, int b, int ind) {
    G[a].push_back(b);
    G[b].push_back(a);

    if (!edges_ind[Edge(a, b)]) edges_ind[Edge(a, b)] = ind;
    else is_multiple_edge[edges_ind[Edge(a, b)]] = true;
}

void dfs(int v, int p = -1) {// Помимо текущей вершины, добавим прямого предка (изначально считаем, что его нет)
    T++;
    best_up[v] = tin[v] = T;
    used[v] = true;
    int children = 0;
    for (auto u: G[v]) {
        if (u == p) continue;
        if (used[u]) {
            best_up[v] = std::min(best_up[v], tin[u]);
        } else {
            dfs(u, v);
            children++;

            best_up[v] = std::min(best_up[v], best_up[u]);
            if (p != -1 && best_up[u] >= tin[v]) { // Условие точки сочленения, когда v - не корень
                art_points.insert(v);
            }
        }
    }
    if (p == -1 && children > 1) {
        // Если v корень и количество его сыновей в дереве поиска больше 1, то вершина v является точкой сочленения
        // Если корень с детьми удалить, то его поддеревья станут несвязными между собой
        art_points.insert(v);
    }
}

void paint(int v, int color, int parent = -1) {
    visited[v] = true;
    for (auto u: G[v]) {
        if (u == parent) continue;
        if (!visited[u]) {
            if (best_up[u] >= tin[v] && !is_multiple_edge[edges_ind[Edge(v, u)]]) {
                max_color++;
                colors[edges_ind[Edge(v, u)]] = max_color;
                paint(u, max_color, v);
            } else {
                colors[edges_ind[Edge(v, u)]] = color;
                paint(u, color, v);
            }
        } else if (tin[u] < tin[v] && !is_multiple_edge[edges_ind[Edge(v, u)]]) {
            colors[edges_ind[Edge(v, u)]] = color;
        }
    }
}


void find_art_points() {
    T = 1;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) dfs(i);
    }
}

void solve() {
    find_art_points();

    max_color = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            paint(i, max_color);
        }
    }
}


int main() {
    fast_cin();

    std::cin >> n >> m;

    G.resize(n + 1);
    used.resize(n + 1);
    best_up.resize(n + 1);
    tin.resize(n + 1);
    visited.resize(n + 1);
    is_multiple_edge.resize(m + 1);

    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;

        add_edge(a, b, i);
    }

    solve();
    std::cout << max_color << "\n";
    for (auto [_, comp]: colors) {
        std::cout << comp << " ";
    }

    return 0;
}

Заранее спасибо.

Answer 1

Короче, я создал монстра...

Начал хранить индексы ребер в виде мапы: [Ребро] : [Множество индексов ребер, кратных ребру из ключа]; затем, когда я хотел красить одно ребро из этого множества, красил их всех, т.к. по факту это одно ребро. Наверняка можно красивее, но давайте я оставлю так:

#include <iostream>
#include <vector>
#include <map>
#include <set>

#define fast_cin() std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL)

int n, m, T;
std::vector<std::vector<int>> G;
std::vector<bool> used, visited;
std::vector<int> best_up, tin, colors;
std::set<int> art_points;
std::map<std::pair<int, int>, std::vector<int>> edges_ind;

int max_color;

std::pair<int, int> Edge(int a, int b) {
    if (a > b) std::swap(a, b);
    return {a, b};
}

void add_edge(int a, int b, int ind) {
    G[a].push_back(b);
    G[b].push_back(a);

    edges_ind[Edge(a, b)].push_back(ind);
}

void dfs(int v, int p = -1) {// Помимо текущей вершины, добавим прямого предка (изначально считаем, что его нет)
    T++;
    best_up[v] = tin[v] = T;
    used[v] = true;
    int children = 0;
    for (auto u: G[v]) {
        if (u == p) continue;
        if (used[u]) {
            best_up[v] = std::min(best_up[v], tin[u]);
        } else {
            dfs(u, v);
            children++;

            best_up[v] = std::min(best_up[v], best_up[u]);
            if (p != -1 && best_up[u] >= tin[v]) { // Условие точки сочленения, когда v - не корень
                art_points.insert(v);
            }
        }
    }
    if (p == -1 && children > 1) {
        // Если v корень и количество его сыновей в дереве поиска больше 1, то вершина v является точкой сочленения
        // Если корень с детьми удалить, то его поддеревья станут несвязными между собой
        art_points.insert(v);
    }
}

void paint(int v, int color, int parent = -1) {
    visited[v] = true;
    for (auto u: G[v]) {
        if (u == parent) continue;
        if (!visited[u]) {
            if (best_up[u] >= tin[v]) {
                max_color++;
                for (auto ind: edges_ind[Edge(v, u)]) {
                    colors[ind] = max_color;
                }
                paint(u, max_color, v);
            } else {
                for (auto ind: edges_ind[Edge(v, u)]) {
                    colors[ind] = color;
                }
                paint(u, color, v);
            }
        } else if (tin[u] < tin[v]) {
            for (auto ind: edges_ind[Edge(v, u)]) {
                colors[ind] = color;
            }
        }
    }
}


void find_art_points() {
    T = 1;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) dfs(i);
    }
}

void solve() {
    find_art_points();

    max_color = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            paint(i, max_color);
        }
    }
}


int main() {
    fast_cin();

    std::cin >> n >> m;

    G.resize(n + 1);
    used.resize(n + 1);
    best_up.resize(n + 1);
    tin.resize(n + 1);
    visited.resize(n + 1);
    colors.resize(m + 1);

    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;

        add_edge(a, b, i);
    }

    solve();
    std::cout << max_color << "\n";
    for (int i = 1; i < colors.size(); i++) {
        std::cout << colors[i] << " ";
    }

    return 0;
}

БЛОГ НА HUSL

Компоненты вершинной двусвязности

Ответы (1 шт):