Cod sursa(job #2791232)

Utilizator PaduraruCristianPaduraru Cristian Daniel PaduraruCristian Data 30 octombrie 2021 11:34:22
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;


ifstream f("biconex.in");
ofstream g("biconex.out");


class Graph{
private:
    int n;
    vector < vector<int> > la;

    vector<vector<int>> componente_biconexe;
    vector<int> lowest, level, father;
    stack<pair<int,int>> edges_biconexe;
    int nr_comp_biconexe;

    void dfs(int nod_crt, vector<bool> &viz);
    void dfs_biconexe(int nod_crt);

public:
    Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1), lowest(0), level(0), father(0), nr_comp_biconexe(0), componente_biconexe(0){}
    ~Graph() = default;

    void add_edge(int from, int to){
        la[from].push_back(to);
    }
    void bfs_print_dist(int start); // Starting from node 1
    int nr_conexe_dfs();
    void print_sortare_topologica(ostream &out);
    void print_comp_biconexe_udg(ostream &out);
};


void Graph::bfs_print_dist(int start)
{
    vector<int> dist(n+1,0);
    queue<int> q;
    int nod_crt;

    q.push(start);
    dist[start]=1;

    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin: la[nod_crt])
        {
            if(dist[nod_vecin] == 0)
            {
                dist[nod_vecin] = dist[nod_crt] + 1;
                q.push(nod_vecin);
            }
        }
    }

    for(int i=1;i<=n;++i)
        g<<dist[i]-1<<' ';
}

int Graph::nr_conexe_dfs()
{

    vector<bool> viz(n+1, false);
    int nr_c=0;
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            ++nr_c;
            dfs(i, viz);
        }
    }

    return nr_c;
}


void Graph::print_sortare_topologica(ostream &out)
{
    queue<int> zero_nodes;
    int grades[n+1] = {0}, i;
    int nod_curent;
    for(i=1;i<=n;++i)
    {
        for(auto nod_vecin: la[i])
            ++grades[nod_vecin];
    }
    for(i=1; i<=n;++i)
        if(grades[i] == 0)
            zero_nodes.push(i);
    if(zero_nodes.empty())
    {
        cout<<"Cyclic Graph. Can't sort.";
        return;
    }
    while(!zero_nodes.empty())
    {
        nod_curent = zero_nodes.front();
        zero_nodes.pop();
        out<<nod_curent<<' ';

        for(auto nod_vecin: la[nod_curent])
        {
            --grades[nod_vecin];
            if(grades[nod_vecin] == 0)
                zero_nodes.push(nod_vecin);
        }
    }
}

void Graph::dfs(int nod_crt, vector<bool> &viz)
{

    for(auto nod_vecin: la[nod_crt])
    {
        if(!viz[nod_vecin])
        {
            viz[nod_vecin] = true;
            dfs(nod_vecin, viz);
        }
    }

}


void Graph::dfs_biconexe(int nod_crt)
{
    level[nod_crt] = level[father[nod_crt]] + 1;
    lowest[nod_crt] = level[nod_crt];

    for(auto nod_vecin: la[nod_crt])
    {
        if(level[nod_vecin] == 0)
        {
            father[nod_vecin] = nod_crt;
            edges_biconexe.push(make_pair(nod_crt, nod_vecin));

            dfs_biconexe(nod_vecin);

            if(lowest[nod_vecin] >= level[nod_crt])
            {
                int a,b;
                ++nr_comp_biconexe;
                vector<int> componenta_biconexa;
                do
                {
                    a=edges_biconexe.top().first;
                    b=edges_biconexe.top().second;

                    edges_biconexe.pop();

                    componenta_biconexa.push_back(a);
                    componenta_biconexa.push_back(b);

                }while(a!=nod_crt && b!=nod_vecin && !edges_biconexe.empty());

                sort(componenta_biconexa.begin(), componenta_biconexa.end());
                componente_biconexe.push_back(componenta_biconexa);
            }
            else
                lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(nod_vecin!= father[nod_crt])
            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);;
    }


}

void Graph::print_comp_biconexe_udg(ostream &out)
{
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);
    father.resize(n+1, 0);

    dfs_biconexe(1);

    out<<nr_comp_biconexe<<'\n';
    for(auto x:componente_biconexe)
    {
        out<<x[0];
        for(int i=1;i<x.size();++i)
            if(x[i]!=x[i-1])
                out<<' '<<x[i];
        out<<'\n';
    }
}




int main()
{
    int n,m;
    int a,b;
    f>>n>>m;

    Graph gr(n);

    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        gr.add_edge(a,b);
        gr.add_edge(b,a);
    }
    f.close();
    gr.print_comp_biconexe_udg(g);
    g.close();
    return 0;
}