Cod sursa(job #2396563)

Utilizator vlad_schillerSchiller Vlad Radu vlad_schiller Data 3 aprilie 2019 17:02:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define muc 100005
using namespace std;

vector <int > G[muc];
vector <int > gfin[muc];
stack <int > s;
int n,m,nrfin,niv[muc],dm[muc];
ifstream f("biconex.in");
ofstream g("biconex.out");
bool viz[muc];

void citire()
{
    int x,y;
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void afis()
{
    g<<nrfin<<'\n';
    for(int i=1;i<=nrfin;i++)
    {
        for(auto j:gfin[i])
            g<<j<<' ';
        g<<'\n';
    }
}

void dfs(int ncr, int tat)
{
    niv[ncr]=niv[tat]+1;
    viz[ncr]=1;
    s.push(ncr);
    dm[ncr]=niv[ncr];
    for(auto i: G[ncr])
    {
        if(i==tat)
            continue;
        if(viz[i])
        {
            dm[ncr]=dm[ncr]<niv[i]? dm[ncr] : niv[i];
            continue;
        }
        dfs(i,ncr);
        dm[ncr]=dm[ncr]<dm[i]? dm[ncr] : dm[i];
        if(niv[ncr]<=dm[i])
        {
            nrfin++;
            int aux;
            do
            {
                aux=s.top();
                s.pop();
                gfin[nrfin].push_back(aux);
            }while(!s.empty()&&aux!=i);
            gfin[nrfin].push_back(ncr);
        }
    }
}

int main()
{
    citire();
    dfs(1,0);
    afis();
    return 0;
}