Cod sursa(job #2763010)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 11 iulie 2021 02:02:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m, ops, nivel[100005], nivelmin[100005], nr;
vector <int> Muchii[100005];
vector <int> comp[100005];
bool v[100005];
stack <pair <int, int>> s;

void dfs(int nod)
{
    v[nod] = true;
    nivelmin[nod] = nivel[nod];
    for(auto k : Muchii[nod])
    {
        if(!v[k])
        {
            nivel[k] = nivel[nod] + 1;
            s.push(make_pair(nod, k));
            dfs(k);
            if(nivelmin[k] >= nivel[nod])
            {
                nr++;

                while(s.top().x != nod || s.top().y != k)
                {
                    comp[nr].push_back(s.top().y);
                    s.pop();
                }

                comp[nr].push_back(nod);
                comp[nr].push_back(k);
                s.pop();

            }

            nivelmin[nod] = min(nivelmin[nod], nivelmin[k]);
        }
        else
            nivelmin[nod] = min(nivelmin[nod], nivel[k]);
    }
}

int main()
{

    f >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        Muchii[x].push_back(y);
        Muchii[y].push_back(x);
    }

    dfs(1);

    g << nr << "\n";
    for(int i = 1; i <= nr; i++, g << "\n")
    {
        for(auto k : comp[i])
            g << k << " ";
    }


    return  0;
}