Компоненты двусвязности, мосты, точки сочленения в неор графе без кратных ребер и петлей

// Неориентированный граф, не содержащий точек сочленения, называется двусвязным
// Компонента двусвязности <=> какое-то кол-во реберно пересекающихся циклов
// Дерево обхода будет содержать только обратные ребра(помимо ребер дерева)
// Если (v,to) обратное ребро - при помощи снма мерджим все ребра на пути от v до to(пропуская уже смердженные)

// чтобы получить мосты берем компоненты из 1 ребра

// чтобы получить точки сочленения берем все вершины лежащие как минимум в 2 компонентах

const ll N = 2e5 + 100;
ll p[N], sz[N], top[N], h[N];

ll get(ll v) {
    if (p[v] == v)
        return v;
    return (p[v] = get(p[v]));
}

void merge(ll a, ll b) {
    a = get(a);
    b = get(b);
    if (a == b)return;
    if (sz[a] < sz[b])swap(a, b);

    if (h[top[b]] < h[top[a]])
        top[a] = top[b];
    p[b] = a;
    sz[a] += sz[b];
}

vector<prll> g[N];
ll used[N], p_ed[N];
prll edges[N];
ll n, m;

void dfs(ll v) {
    used[v] = 1;
    for (auto& el : g[v]) {
        ll to = el.first;
        ll id = el.second;
        if (used[to]) { // обратное ребро
            if ((h[v] - h[to]) <= 1)continue; // ребро в прямого предка <=> нет проверки
            assert(sz[id] == 1);
            top[id] = v; // подходит любая с >=h[v]
            ll cur = v;
            while (h[cur] > h[to]) { // мерджим ребра
                merge(id, p_ed[cur]);
                cur = top[get(id)];
            }
        }
        else {
            p_ed[to] = id;
            assert(sz[id] == 1);
            top[id] = v;
            h[to] = h[v] + 1;
            dfs(to);
        }
    }
}

vector<ll> ans[N];

void $main()
{
    cin >> n >> m;
    for (ll i = 0; i < m; ++i) {
        ll v, u; cin >> v >> u;
        --v; --u;
        g[v].emplace_back(u, i);
        g[u].emplace_back(v, i);
        edges[i] = m_p(v, u);

        sz[i] = 1;
        p[i] = i;
    }
    for (ll i = 0; i < n; ++i)
        if (!used[i])
            p_ed[i] = -1, dfs(i);

    for (ll i = 0; i < m; ++i)
        ans[get(i)].push_back(i);

    // Компоненты двусвязности
    /*ll sz_ans = 0;
    for (ll i = 0; i < m; ++i)
        sz_ans += !ans[i].empty();

    cout << sz_ans << '\n';
    for (ll i = 0; i < m; ++i) {
        if (ans[i].empty())continue;
        assert(sz[i] == (ll)ans[i].size());
        cout << sz[i] << '\n';
        for (ll id : ans[i])
            cout << edges[id].first + 1 << " " << edges[id].second + 1 << '\n';
    }*/

    // Мосты
    /*ll sz_ans = 0;
    for (ll i = 0; i < m; ++i)
        sz_ans += ((ll)ans[i].size() == 1);

    cout << sz_ans << '\n';
    for (ll i = 0; i < m; ++i) {
        if ((ll)ans[i].size() != 1)continue;
        for (ll id : ans[i])
            cout << id + 1 << " ";
    }*/

    // Точки сочленения + нужно ll vita[N], good[N];
    /*for (ll i = 0; i < n; ++i)
        vita[i] = -1;

    for (ll i = 0; i < m; ++i) {
        for (ll id : ans[i]) {
            ll a = edges[id].first;
            ll b = edges[id].second;
            if (vita[a] != i && vita[a] != -1)
                good[a] = 1;
            if (vita[b] != i && vita[b] != -1)
                good[b] = 1;

            vita[a] = vita[b] = i;
        }
    }
    ll sz_ans = 0;
    for (ll i = 0; i < n; ++i)
        sz_ans += good[i];
    cout << sz_ans << '\n';
    for (ll i = 0; i < n; ++i)
        if (good[i])
            cout << i + 1 << " ";*/
}