Cod sursa(job #2717607)

Utilizator Costea_AlexandruCostea Alexandru Costea_Alexandru Data 7 martie 2021 17:51:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
int p,n,m,niv[100001],nma[100001],vz[100001],vf,sl;
vector<int>v[100001],st, sol1[100001];
void Citire()
{
    int i,j;
    fi >> n >> m;
    while(fi >> i >> j)
    {
        v[i].push_back(j);
        v[j].push_back(i);
    }
}
void DFS(int nod, int t, int rad)
{
    int x, i;
    vz[nod]++;
    vf++;
    st.push_back(nod);
    niv[nod] = niv[t]+1;
    nma[nod] = niv[nod];
    for(i=0; i<v[nod].size(); i++)
    {
        x = v[nod][i];
        if(x!=t)
        {
            if(vz[x])
            {
                if(nma[nod] > niv[x])
                    nma[nod] = niv[x];
            }
            else
            {
                DFS(x,nod,rad);
                if(nma[nod] > nma[x])
                    nma[nod] = nma[x];
                if(niv[nod] <= nma[x])
                {
                    sl++;
                    while(st[vf] != x)
                    {
                        sol1[sl].push_back(st[vf]);
                        st.pop_back();
                        vf--;
                    }
                    sol1[sl].push_back(x);
                    st.pop_back();
                    vf--;
                    sol1[sl].push_back(nod);
                }
            }
        }
    }
}
int main()
{
    int i,j;
    Citire();
    vf = -1;
    DFS(1,0,1);
    fo << sl << '\n';
    for(i=1; i<=sl; i++)
    {
        for(j=0; j<sol1[i].size(); j++)
            fo << sol1[i][j] << " ";
        fo << '\n';
    }
    return 0;
}