Cod sursa(job #2792862)

Utilizator PaduraruCristianPaduraru Cristian Daniel PaduraruCristian Data 2 noiembrie 2021 13:34:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.7 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<vector<int>> componente_tconexe;
    vector<int> lowest, level, father, degrees;
    vector<bool> onstack;
    stack<int> S;
    stack<pair<int,int>> edges_biconexe;
    int index;

    void dfs(int nod_crt, vector<bool> &viz);
    void dfs_biconexe(int nod_crt);
    void dfs_tarjan(int nod_crt);
    void add_cmp_biconexa(int x, int y);
    bool consume(int nr, int poz);


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

    void add_edge(int from, int to){
        la[from].push_back(to);
    }
    void bfs_print_dist(int start=1); // Starting from node 1
    int nr_conexe_dfs();
    void print_sortare_topologica(ostream &out);
    void print_comp_biconexe_udg(ostream &out);
    void print_comp_tconexe_dg(ostream &out);
    bool Havel_Hakimi(vector<int> &grade_noduri);
};


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;
    degrees.resize(n+1,0);
    int nod_curent, i;
    for(i=1;i<=n;++i)
    {
        for(auto nod_vecin: la[i])
            ++degrees[nod_vecin];
    }
    for(i=1; i<=n;++i)
        if(degrees[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])
        {
            --degrees[nod_vecin];
            if(degrees[nod_vecin] == 0)
                zero_nodes.push(nod_vecin);
        }
    }
    degrees.clear();
}

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::add_cmp_biconexa(int x, int y)
{
    int a,b;
    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!=x || b!=y) && !edges_biconexe.empty());

    sort(componenta_biconexa.begin(), componenta_biconexa.end() );
    componente_biconexe.push_back(componenta_biconexa);
}

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])
                add_cmp_biconexa(nod_crt, nod_vecin);

            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(nod_vecin!= father[nod_crt])
            lowest[nod_crt] = min(lowest[nod_crt], level[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<<componente_biconexe.size()<<'\n';
    for(auto componenta:componente_biconexe)
    {
        out<<componenta[0];
        for(int i=1;i<componenta.size();++i)
            if(componenta[i]!=componenta[i-1])
                out<<' '<<componenta[i];
        out<<'\n';
    }

    lowest.clear();
    level.clear();
    father.clear();
}



void Graph::dfs_tarjan(int nod_crt)
{
    ++index;
    level[nod_crt] = index;
    lowest[nod_crt] = index;
    S.push(nod_crt);
    onstack[nod_crt] = true;

    for(auto nod_vecin : la[nod_crt])
    {
        if(level[nod_vecin]==0)
        {
            dfs_tarjan(nod_vecin);
            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(onstack[nod_vecin])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);
    }

    if(level[nod_crt] == lowest[nod_crt])
    {
        vector<int> comp_tconexa;
        int st;
        do
        {
            st = S.top();
            S.pop();
            onstack[st]=false;
            comp_tconexa.push_back(st);
        }while(st!=nod_crt);

        componente_tconexe.push_back(comp_tconexa);
    }

}

void Graph::print_comp_tconexe_dg(ostream &out)
{
    onstack.resize(n+1, false);
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);

    for(int i=1;i<=n;++i)
    {
        if(level[i] == 0)
        {
            dfs_tarjan(i);
        }
    }
    out<<componente_tconexe.size()<<'\n';
    for(auto comp: componente_tconexe)
    {
        for(auto nod:comp)
            out<<nod<<' ';
        out<<'\n';
    }
    onstack.clear();
    lowest.clear();
    level.clear();
}


bool Graph::consume(int nr, int poz)
{
    if(nr == 0)
        return true;
    if(poz == 0)
        return false;

    if(nr>degrees[poz])
    {
        bool ok = consume(n-degrees[poz], poz-1);
        degrees[poz-1]+=degrees[poz];
        degrees[poz]=0;
        return ok;
    }

    degrees[poz-1]+=nr;
    degrees[poz]  -=nr;

    return true;
}

bool Graph::Havel_Hakimi(vector<int>& grade_noduri)
{
    int sum=0, max_grade = 0;
    degrees.resize(n, 0);
    for(auto x: grade_noduri)
    {
        if(x>=n)
        {
            degrees.clear();
            return false;
        }

        ++degrees[x];
        sum+=x;

        if(x>max_grade)
            max_grade = x;
    }
    if( sum & 1)
    {
        degrees.clear();
        return false;
    }
    if(max_grade <=1 )
    {
        degrees.clear();
        return true;
    }

    for(int i=max_grade; i; --i)
    {
        while(degrees[i])
        {
            --degrees[i];
            if( !consume(i, i) )
            {
                degrees.clear();
                return false;
            }
        }
    }
    degrees.clear();
    return true;
}


int get_degrees(const char* f_name, vector<int>& v)
{
    ifstream in(f_name);
    int n,m,a,b;
    in>>n>>m;
    v.resize(n, 0);

    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        ++v[a-1];
        ++v[b-1];
    }

}

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

    f>>n;
    f>>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;
}