Cod sursa(job #2857080)

Utilizator norryna07Alexandru Norina norryna07 Data 24 februarie 2022 20:38:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <vector>
#include <fstream>
#include <bitset>
#include <stack>
using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

vector < vector <int> > g;
vector <int> dist, low;
vector < vector <int> > cmp;
bitset <100005> viz;
stack <int> s;
int n, m, nrc;

void citire()
{
    fin>>n>>m;
    g = vector  < vector <int> > (n+2);
    dist = vector <int> (n+2);
    low = vector <int> (n+2);
    int x, y;
    for (int i=1; i<=m; ++i) 
    {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int x, int f, int r)
{
    viz[x]=1;
    dist[x]=low[x]=dist[f]+1;
    s.push(x);
    int kids=0;
    for (auto y:g[x])
    {
        if (y==f) continue;
        if (viz[y])
        {
            low[x]=min(low[x], dist[y]);
            continue;
        }

        kids++;
        dfs(y, x, r);
        low[x]=min(low[x], low[y]);

        if (dist[x]<=low[y])
        {
            nrc++;
            cmp.push_back( vector <int> (0));
            int z;
            do 
            {
                z=s.top();  s.pop();
                cmp[nrc-1].push_back(z);
            } while (z!=y);
            cmp[nrc-1].push_back(x);
        }
    }
}

void solve()
{
    for (int i=1; i<=n; ++i)
        if (!viz[i]) dfs(i, 0, i);
    fout<<nrc<<'\n';
    for (int i=0; i<nrc; ++i)
    {
        for(auto x:cmp[i]) fout<<x<<' ';
        fout<<'\n';
    }
}

int main()
{
    citire();
    solve();
    return 0;
}