Cod sursa(job #2793145)

Utilizator alexbrinzaAlexandru Brinza alexbrinza Data 3 noiembrie 2021 02:21:08
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

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

class graph{

    int n, ct;
    vector < vector < int > > G, ReverseG, sol;
    queue < int > Bfs;
    stack < int > Ctc, Topo, Biconex;
    vector < bool > vis, vis2;
    vector < int > level, low;

    void bfs(int source)
    {
        vector < int > nodes;

        nodes.resize(n + 1, -1);

        Bfs.push(source); nodes[source] = 0;

        while(!Bfs.empty())
        {
            int node = Bfs.front();
            Bfs.pop();

            for(int i = 0; i < G[node].size(); ++i)
            {
                int nnode = G[node][i];
                if(nodes[nnode] == -1)
                {
                    nodes[nnode] = nodes[node] + 1;
                    Bfs.push(nnode);
                }
            }
        }

        for(int i = 1; i <= n; ++i)
            out << nodes[i] << " ";
    }

    void dfs(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs(nnode);
        }
    }

    void dfs_ctc_1(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs_ctc_1(nnode);
        }

        Ctc.push(node);
    }

    void dfs_ctc_2(int node)
    {
        vis2[node] = 1;
        sol[ct - 1].push_back(node);

        for(int i = 0; i < ReverseG[node].size(); ++i)
        {
            int nnode = ReverseG[node][i];

            if(vis2[nnode] == 0)
                dfs_ctc_2(nnode);
        }
    }

    void dfs_topo(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs_topo(nnode);
        }

        Topo.push(node);
    }

    void dfs_biconex(int node, int dad)
    {
        vis[node] = 1;
        level[node] = level[dad] + 1;
        low[node] = level[node];

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(nnode != dad)
            {
                if(vis[nnode] == 1)
                {
                    if(level[nnode] < low[node])
                        low[node] = level[nnode];
                }
                else
                {
                    Biconex.push(nnode);

                    dfs_biconex(nnode, node);

                    if(low[nnode] < low[node])
                        low[node] = low[nnode];

                    if(level[node] <= low[nnode])
                    {
                        ++ct;

                        Biconex.push(node);

                        while(!Biconex.empty() && Biconex.top() != nnode)
                        {
                            sol[ct - 1].push_back(Biconex.top());
                            Biconex.pop();
                        }

                        if(!Biconex.empty())
                        {
                            sol[ct - 1].push_back(Biconex.top());
                            Biconex.pop();
                        }
                    }
                }
            }
        }
    }

public:

    void solve_bfs()
    {
        int m, s, x, y;

        in >> n >> m >> s;

        G.resize(n + 1);

        for(int i = 0; i < m; ++i)
        {
            in >> x >> y;
            G[x].push_back(y);
        }

        bfs(s);
    }

    void solve_dfs()
    {
        int m, x, y, ct = 0;

        in >> n >> m;

        G.resize(n + 1);
        vis.resize(n + 1, false);

        for(int i = 0; i < m; ++i)
        {
            in >> x >> y;

            G[x].push_back(y);
            G[y].push_back(x);
        }

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
            {
                ++ct;
                dfs(i);
            }

        out << ct;
    }

    void solve_ctc()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        ReverseG.resize(n + 1);
        sol.resize(n + 1);
        vis.resize(n + 1, false);
        vis2.resize(n + 1, false);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y;

            G[x].push_back(y);
            ReverseG[y].push_back(x);
        }

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
                dfs_ctc_1(i);

        ct = 0;

        while(!Ctc.empty())
        {
            int node = Ctc.top();
            Ctc.pop();

            if(vis2[node] == 0)
            {
                ++ct;
                dfs_ctc_2(node);
            }
        }

        out << ct << "\n";

        for(int i = 0; i < ct; ++i)
        {
            for(int j = 0; j < sol[i].size(); ++j)
                out << sol[i][j] << " ";

            out << "\n";
        }
    }

    void solve_topo()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        vis.resize(n + 1, false);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y;
            G[x].push_back(y);
        }

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
                dfs_topo(i);

        while(!Topo.empty())
        {
            int node = Topo.top();
            Topo.pop();

            out << node << " ";
        }
    }

    void solve_biconex()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        sol.resize(n + 1);
        level.resize(n + 1, 0);
        low.resize(n + 1, 0);
        vis.resize(n + 1, false);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }

        ct = 0;

        dfs_biconex(1, 0);

        out << ct << "\n";

        for(int i = 0; i < ct; ++i)
        {
            for(int j = 0; j < sol[i].size(); ++j)
                out << sol[i][j] << " ";

            out << "\n";
        }

    }

};

int main()
{
    graph G;
    G.solve_biconex();
    return 0;
}