Cod sursa(job #2679801)

Utilizator andrei_laurentiuRadu Andrei-Laurentiu andrei_laurentiu Data 1 decembrie 2020 15:32:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.73 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;

const int nmax = 100005;

vector<int> lis_vec[nmax];
vector<int> discover, low, art_vertex, parent, sol;
int timp, Root, rootChildren, nr_comp_biconexe;

struct muchie
{
    int a, b;
};
muchie aux;
stack<muchie> st;
vector<int> componente[nmax];
ifstream fin("biconex.in");
ofstream fout("biconex.out");

void art_Point(int u)
{
    int j, v;
    ++timp;
    discover[u] = timp;//timpul descoperirii
    low[u] = timp;//low_time initial
    for(j = 0; j < lis_vec[u].size(); ++j)
    {
        v = lis_vec[u][j];// v e copilul lui u
        if(!discover[v])
        {
            aux.a = u;
            aux.b = v;
            st.push(aux);//punem in stiva pana cand

            parent[v] = u;//tatal lui v e u
            if(u == Root)//1 // numaram cati fii are radacina(daca radacina are 1 sau 0 fii atunci este punct de articulatie)
                ++rootChildren;
            art_Point(v);//apelare dfs
            //dupa ce realizam parcurgerea pornim de la ultimul nod in care am ajuns

            if(low[v] >= discover[u])//daca u este punct de articulatie
            {
                ++nr_comp_biconexe;
                do
                {
                    componente[nr_comp_biconexe].push_back(st.top().b);//punem v-ul in componenta
                    aux = st.top();
                    st.pop();
                }while(!(st.empty() || aux.a == u || aux.b == v));//cat timp nu s-a golit stiva sau am ajuns la unul dintre nodurile u si v
                componente[nr_comp_biconexe].push_back(aux.a);

                art_vertex[u] = 1;
            }
            if(low[u] > low[v]) //"mostenesc" low_time-ul CAND FAC INTOARCEREA
                low[u] = low[v];
        }
        else if(v != parent[u])
        {
            if(low[u] > discover[v])
                low[u] = discover[v];
        }
    }
}
int main()
{
    int m, n, u, v, i;
    fin>>n>>m;
    for(i = 1; i <= m; ++i)
    {
        fin>>u>>v;
        lis_vec[u].push_back(v);
        lis_vec[v].push_back(u);
    }
    parent.assign(n+1, 0);
    art_vertex.assign(n+1, 0);
    low.assign(n+1, 0);
    discover.assign(n+1, 0);

    for(i = 1; i <= n; ++i)
    {
        if(!discover[i])
        {
            Root = i;
            rootChildren = 0;
            art_Point(i);
            art_vertex[Root] = (rootChildren > 1);
        }
    }
    fout<<nr_comp_biconexe<<'\n';
    for(int i = 1;i <= nr_comp_biconexe;i++)
    {
        for(int j = 0;j < componente[i].size();j++)
            fout<<componente[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}//frunza nu e niciodata punct de articulatie