Cod sursa(job #3030016)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 17 martie 2023 13:21:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i, j, ncbc, x, y;
vector <vector <int> > g;
vector <set <int> > cbc;
set <int> toPush;
vector <int> viz, lvl,  t, mnl;
stack <pair <int, int> > s;
void dfs (int x, int l)
{
    viz[x] = 1;
    lvl[x] = l;
    mnl[x] = l;
    for (auto it : g[x])
    {
        if (viz[it] == 0)
        {
            s.push({x, it});
            dfs (it, l+1);
            mnl[x] = min(mnl[x], mnl[it]);
            if (mnl[it] >= lvl[x])
            {
                ncbc++;
                toPush.clear();
                int xx, yy;
                do
                {
                    xx = s.top().first, yy = s.top().second;
                    s.pop();
                    toPush.insert(xx); toPush.insert(yy);
                }
                while (xx != x || yy != it);
                cbc.push_back(toPush);
            }
        }
        else if (it != t[x])
        {
            mnl[x] = min(mnl[x], lvl[it]);
        }
    }
}
int main()
{
    fin >> n >> m; g.resize(n+1); cbc.resize(1); t.resize(n+1); viz.resize(n+1); lvl.resize(n+1); mnl.resize(n+1);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (i = 1; i <= n; i++)
    {
        if (!viz[i])
            dfs (i, 1);
    }
    fout << ncbc << '\n';
    for (i = 1; i <= ncbc; i++)
    {
        for (auto it : cbc[i])
            fout << it << ' ';
        fout << '\n';
    }
    return 0;
}