Cod sursa(job #2664403)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 28 octombrie 2020 16:30:05
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <stack>
#include <vector>

constexpr auto max_n = 100005;

using namespace std;

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

int n, m;
vector<int> graph[max_n];
stack<pair<int, int>> stk;
int level[max_n];
int above[max_n];

vector<vector<int>> sub_graphs;

void handle_sub_graph(const pair<int, int> nodes)
{
    vector<int> con;
    int tx, ty;
    do
    {
        tx = stk.top().first;
        ty = stk.top().second;
        stk.pop();
        con.push_back(ty);
    } while (tx != nodes.first || ty != nodes.second);

    con.push_back(tx);

    sub_graphs.push_back(con);
}

void dfs(const int node, const int lv)
{
    level[node] = lv;
    above[node] = lv;

    for (auto neighbor : graph[node])
    {
        if (level[neighbor] == -1)
        {
            stk.push(make_pair(node, neighbor));
            dfs(neighbor, lv + 1);

            above[node] = min(above[node], above[neighbor]);

            if (above[neighbor] >= level[node])
                handle_sub_graph(make_pair(node, neighbor));
        }
        else
            above[node] = min(above[node], level[neighbor]);
    }
}

int main()
{
    fin >> n >> m;

    for (auto i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for (auto i = 0; i <= n; i++)
        level[i] = -1;

    dfs(1, 0);

    fout << sub_graphs.size() << "\n";

   for (const auto& sub_graph : sub_graphs)
    {
        for (auto node : sub_graph)
            fout << node << " ";
        fout << "\n";
    }
    return 0;
}