Cod sursa(job #2715323)

Utilizator mara_cimpeanMara Cimpean mara_cimpean Data 3 martie 2021 15:36:49
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector <int> v[100010];
vector <pair<int,int>> c;
vector <vector<int>> b;
stack<int> st;

int n,m,nrbi;
bool critical[100010],viz[100010];
int niv[100010], nmin[100010];

void dfs(int nod, int tata, int rad)
{
    int aux,cnt=0;
    viz[nod]=1;
    niv[nod]=nmin[nod]=niv[tata]+1;
    st.push(nod);

    for (vector<int>::iterator i=v[nod].begin();i!=v[nod].end();i++)
    {
        if (*i!=tata)
        {
            if (viz[*i])
            {
                if (nmin[nod]>niv[*i])
                    nmin[nod]=niv[*i];
            }
            else
            {
                cnt++;
                dfs(*i,nod,rad);
                if (nmin[nod]>nmin[*i])
                    nmin[nod]=nmin[*i];

                if (niv[nod]<nmin[*i])
                    c.push_back((make_pair(nod,*i)));

                if (niv[nod]<=nmin[*i])
                {
                    nrbi++;
                    b.push_back(vector<int>(0));
                    do
                    {
                        aux=st.top();
                        st.pop();
                        b[nrbi-1].push_back(aux);
                    } while(aux!=*i);

                    b[nrbi-1].push_back(nod);
                    if (nod!=rad)
                        critical[nod]=1;
                }
            }
        }
    }

    if (nod==rad && cnt>1)
        critical[nod]=1;
}

int main()
{
    int i,j,x,y,cnt=0;
    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++)
        if (viz[i]==0)
            dfs(i, 0, i);

    fout<<nrbi<<'\n';
    for (i=0;i<nrbi;i++)
    {
        ///fout<<b[i].size()<<" ";
        for (j=0;j<b[i].size();j++)
            fout<<b[i][j]<<" ";
        fout<<'\n';
    }

    return 0;
}