Cod sursa(job #3196413)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 23 ianuarie 2024 20:06:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.2 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5 +7;
vector<int> g[nmax];

int depth[nmax],viz[nmax],low[nmax];
int rad = 1;

void dfs_depth(int nod, int tata, int adancime)
{
    depth[nod] = adancime;
    viz[nod] = 1;
    for(auto vecin: g[nod])
    {
        if(vecin == tata || viz[vecin]) continue;
        dfs_depth(vecin, nod, adancime + 1);
    }
}

void dfs_low(int nod, int tata)
{
    low[nod] = depth[nod];
    for(auto vecin: g[nod]) //muchie verde
    {
        if(vecin == tata || depth[vecin] == depth[nod] + 1) continue;
        //am dat de o muchie de intoarcere!
        low[nod] = min(low[nod], depth[vecin]);
    }

    for(auto vecin: g[nod]) //muchie rosie
    {
        if(depth[vecin] != depth[nod] + 1) continue;
        dfs_low(vecin, nod);
        low[nod] = min(low[nod], low[vecin]);
    }
}

vector<int> critice;
void dfs_critice(int nod)
{
    bool e_critic = 0;
    int nr_fii = 0;
    for(auto vecin: g[nod])
    {
        if(depth[vecin] == depth[nod] + 1)
        {
            nr_fii++;
            dfs_critice(vecin);
        }
        if(low[vecin] >= depth[nod]) //nu reusesc sa urc mai sus de nod
        {
            e_critic = 1;
        }
    }
    if(nod == rad && nr_fii >= 2) e_critic = 1; //daca radacina are mai mult de 2 fii
    if(e_critic) critice.push_back(nod);
}

vector<pair<int,int> > poduri;

void dfs_poduri(int nod)
{
    for(auto vecin: g[nod])
    {
        if(depth[vecin] == depth[nod] + 1)
        {
            if(low[vecin] > depth[nod]) //nu reusesc nici macar sa ma intorc la nod
            {
                poduri.push_back({nod,vecin});
            }
            dfs_poduri(vecin);
        }
    }
}

stack<int> dfs_stack;
vector<vector<int> > biconexe;

void dfs_biconexe(int nod)
{
    dfs_stack.push(nod);

    for(auto vecin: g[nod])
    {
        if(depth[vecin] == depth[nod] + 1)
        {
            dfs_biconexe(vecin);

            if(low[vecin] >= depth[nod]) //nu reusesc sa ma intorc mai sus
            { //deci am ceva ciclu chiar sub nodul meu
                //am gasit o componenta biconexa
                vector<int> comp_biconexa;
                while(dfs_stack.top() != vecin)
                {
                    comp_biconexa.push_back(dfs_stack.top());
                    dfs_stack.pop();
                }
                comp_biconexa.push_back(vecin);
                comp_biconexa.push_back(nod);
                dfs_stack.pop();

                biconexe.push_back(comp_biconexa);
            }
        }
    }
}

int main()
{
    int n,m; fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y; fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs_depth(rad,0,1);
    dfs_low(rad,0);
    dfs_critice(rad);
    dfs_poduri(rad);
    dfs_biconexe(rad);
    fout<<biconexe.size()<<"\n";
    for(auto comp_biconexa : biconexe)
    {
        sort(comp_biconexa.begin(), comp_biconexa.end());
        for(auto nod: comp_biconexa)
        {
            fout<<nod<<" ";
        }
        fout<<"\n";
    }
    return 0;
}