Cod sursa(job #2396521)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 3 aprilie 2019 16:34:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,llk[100010],niv[100010],viz[100010];
stack <int> S;
vector <int> G[100010],comp;
vector <vector <int> >Sol;
void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}
void dfs(int tata, int nod)
{
    S.push(nod);
    niv[nod]=niv[tata]+1;
    viz[nod]=1;
    llk[nod]=niv[nod];
    for(auto v:G[nod])
    {
        if(v==tata) continue;
        if(!viz[v])
        {
            dfs(nod,v);
            llk[nod]=min(llk[nod],llk[v]);
            if(niv[nod]<=llk[v])
            {

                comp.resize(0);
                comp.push_back(nod);
                comp.push_back(v);
                while(S.top()!=v)
                {
                    comp.push_back(S.top());
                    S.pop();
                }
                S.pop();
                Sol.push_back(comp);
            }
        }
        else llk[nod]=min(llk[nod],niv[v]);


    }
}
int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(0,i);
    fout<<Sol.size()<<"\n";
    for(auto v:Sol)
    {
        for(auto g:v)
            fout<<g<<" ";
        fout<<"\n";
    }
    return 0;
}