Cod sursa(job #3223767)

Utilizator TaniaKallosKallos Tania TaniaKallos Data 13 aprilie 2024 16:05:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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


const int N = 1e5;
int n, m;
int lev[N+1], low[N+1];
vector <int> g[N+1];
vector < vector <int> > ans;
stack <int> conex;


void dfs(int node, int daddy)
{
    low[node] = lev[node];
    conex.push(node);
    for (auto vec : g[node])
    {
        if (lev[vec] == 0)
        {
            lev[vec] = lev[node] + 1;
            dfs(vec, node);
            low[node] = min(low[node], low[vec]);

            if (lev[node] <= low[vec])
            {
                vector <int> v;
                while (conex.top() != vec)
                {
                    v.push_back(conex.top());
                    conex.pop();
                }
                v.push_back(vec), conex.pop();
                v.push_back(node);
                ans.push_back(v);
            }
        }
        else
        {
            if (vec != daddy)
                low[node] = min(low[node], lev[vec]);
        }
    }
}


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

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }


    lev[1] = 1;
    dfs(1, -1);


    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++)
    {
        for (int j = 0; j < ans[i].size(); j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }


    return 0;
}