Cod sursa(job #3041000)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 30 martie 2023 19:24:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
///toata lumea baga azi biconexe

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int N = 1e5;
int discover[N + 1], low[N + 1], tata[N + 1];

int n, m, x, y, k;

vector <int> ans[N + 1];

vector <int> g[N + 1];

stack <int> s;

void dfs (int node, int time)
{
    s.push(node);
    discover[node] = low[node] = time;
    for (auto it : g[node])
    {
        if (!discover[it])
        {
            tata[it] = node;
            dfs (it, time + 1);
            ///verific daca e punct de articulatie
            ///practic verific daca fiul are sau nu un stramos
            if (low[it] >= discover[node])
            {
                ///facem comp biconexe
                ans[++k].push_back(node);///punctul de articulatie
                while (!s.empty() && s.top() != it)
                {
                    ans[k].push_back(s.top());
                    s.pop();
                }
                ans[k].push_back(it);
                if (!s.empty())
                    s.pop();
            }
            low[node] = min (low[node], low[it]);
        }
        else
        {
            ///caut stramos
            if (it != tata[node])
                low[node] = min (low[node], discover[it]);
        }
    }
}

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