Cod sursa(job #2983929)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 23 februarie 2023 12:16:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <bitset>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector <int> v[100002],sol[100002];
bitset <100002> viz;
int nivel[100002],ch,m,x,y,low[100002],stiva[100002],k,nrc,i,n,j;
void dfs (int nod,int niv,int tata)
{
    viz[nod]=1;
    low[nod]=nivel[nod]=niv;
    stiva[++k]=nod;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (vecin==tata)
            continue;
        if (viz[vecin]==0)
        {
            dfs (vecin,niv+1,nod);
            low[nod]=min (low[nod],low[vecin]);
            if (nivel[nod]<=low[vecin])
            {
                nrc++;
                do
                {
                    sol[nrc].push_back (stiva[k]);
                    k--;
                }
                while (k>0&&stiva[k+1]!=vecin);
                sol[nrc].push_back (nod);
            }
        }
        else
            low[nod]=min (low[nod],nivel[vecin]);
    }
}
int main ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
    for (i=1; i<=n; i++)
        sort (v[i].begin (),v[i].end ());
    dfs (1,1,0);
    fout<<nrc<<"\n";
    for (i=1; i<=nrc; i++)
    {
        for (j=0; j<sol[i].size (); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}