Cod sursa(job #3271590)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 26 ianuarie 2025 17:39:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

vector<int> G[100005];
int nivel[100005], nma[100005], vis[100005];
stack<int> s;
vector<int> temp;
vector<vector<int>> biconexe;

void dfs(int k, int parent)
{
    vis[k] = 1;
    nivel[k] = nivel[parent] + 1;
    nma[k] = nivel[k];
    s.push(k);

    for(int x : G[k])
    {
        if(x == parent)
            continue;

        if(vis[x])
        {
            if(nma[k] > nivel[x])
                nma[k] = nivel[x];
        }
        else
        {
            dfs(x, k);
            if(nma[k] > nma[x])
                nma[k] = nma[x];

            //if(nivel[k] <= nma[x])
                //cout << k << endl;

            //if(nivel[k] < nma[x])
              //  cout << k << " " << x << endl;

            if(nivel[k] <= nma[x])
            {
                while(s.top() != x)
                {
                    temp.push_back(s.top());
                    s.pop();
                }
                s.pop();
                temp.push_back(x);
                temp.push_back(k);
                biconexe.push_back(temp);
                temp.clear();
            }
        }
    }
}

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

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

    dfs(1, 0);

    cout << biconexe.size() << '\n';
    for(auto i : biconexe)
    {
        for(int j : i)
            cout << j << " ";
        cout << '\n';
    }
    return 0;
}