Cod sursa(job #3216942)

Utilizator solicasolica solica solica Data 20 martie 2024 16:06:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

#define NMAX 100008

int n,i,j,nrcomp,m,a,b;

int depth[NMAX],l[NMAX];

bool viz[NMAX];

vector<int>muchii[NMAX],comp[NMAX];

stack<int>stiva;

void input ();

void dfs(int node, int parent);

int main()
{
    input();
    dfs(1,0);
    fout<<nrcomp<<'\n';
    for (i=1; i<=nrcomp; i++)
    {
        for (auto it : comp[i])
        {
            fout<<it<<' ';
        }
        fout<<'\n';
    }
    return 0;
}

void input ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>a>>b;
        muchii[b].push_back(a),muchii[a].push_back(b);
    }
}

void dfs(int node, int parent)
{
    viz[node]=1;
    depth[node]=l[node]=depth[parent]+1;
    stiva.push(node);
    for (auto vec : muchii[node])
    {
        if (vec!=parent)
        {
            if (viz[vec])
            {
                l[node]=min(l[node],depth[vec]);
            }
            else
            {
                dfs(vec,node);
                l[node]=min(l[node],l[vec]);
                if (l[vec]>=depth[node])
                {
                    nrcomp++;
                    while (stiva.top()!=vec)
                    {
                        comp[nrcomp].push_back(stiva.top());
                        stiva.pop();
                    }
                    comp[nrcomp].push_back(vec);
                    stiva.pop();
                    comp[nrcomp].push_back(node);
                }
            }
        }
    }

}