Cod sursa(job #2870925)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 12 martie 2022 18:32:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m, nr;
int niv[DIM], nivMin[DIM];
stack <pair <int, int>> s;
bitset <DIM> v;
vector <int> cBicon[DIM];
vector <int> edges[DIM];

void dfs(int node)
{
    v[node] = 1;
    nivMin[node] = niv[node];
    for (auto k: edges[node])
    {
        if (!v[k])
        {
            niv[k] = niv[node] + 1;
            s.push(make_pair(node, k));
            dfs(k);
            if (nivMin[k] >= niv[node])
            {
                nr++;
                while (s.top().first != node || s.top().second != k)
                {
                    cBicon[nr].push_back(s.top().second);
                    s.pop();
                }

                cBicon[nr].push_back(node);
                cBicon[nr].push_back(k);
                s.pop();
            }
            nivMin[node] = min(nivMin[node], nivMin[k]);
        }
        else
            nivMin[node] = min(nivMin[node], niv[k]);
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    dfs(1);

    g << nr << "\n";
    for (int i = 1; i <= nr; i++, g << "\n")
    {
        for (auto k: cBicon[i])
            g << k << " ";
    }
    return 0;
}