Cod sursa(job #3226725)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 22 aprilie 2024 17:25:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int N = 1e5;

int low[N + 1], discover[N + 1];

vector <int> g[N + 1], v[N + 1];

stack <int> s;

int n, m, x, y, timp, nr;

void dfs (int node, int parent)
{
    low[node] = discover[node] = ++timp;
    s.push(node);
    for (auto it : g[node])
    {
        if (!discover[it])
        {
            dfs (it, node);
            low[node] = min (low[node], low[it]);
            if (low[it] > discover[node])///(node, it) bridge
                ;///nu poate ajunge undeva mai sus
            if (low[it] >= discover[node])///node e punct de articulatie
            {
                v[++nr].push_back(node);
                while (!s.empty() && s.top() != it)
                    v[nr].push_back(s.top()), s.pop();
                if (!s.empty())
                    v[nr].push_back(s.top()), s.pop();
            }
        }
        else
        {
            if (it != parent)///poate fi stramos
                low[node] = min (low[node], discover[it]);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs (1, 0);
    cout << nr << '\n';
    for (int i = 1; i <= nr; ++i, cout << '\n')
        for (auto it : v[i])
        cout << it << ' ';
    return 0;
}