Cod sursa(job #2694390)

Utilizator altcontnoualt cont altcontnou Data 9 ianuarie 2021 07:24:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>

#include <fstream>

#include <vector>

#include <stack>



using namespace std;



ifstream f("biconex.in");

ofstream g("biconex.out");



vector<int>graph[100005];



stack<int>s;



vector<int>rez[100005];



int k;



bool viz[100005];

int llk[100005], ix[100005];



int n, m, x, y;



void citire()

{

    f >> n >> m;

    for (int i=0; i<m; ++i)

    {

        f >> x >> y;

        graph[x].push_back(y);

        graph[y].push_back(x);

    }

}



void parcurgere(int ind)

{

    viz[ind]=1;

    //llk[ind]=ix[ind]=1;

    for (auto &v:graph[ind])

    {

        if (!viz[v])

        {

            ix[v]=ix[ind]+1;

            llk[v]=ix[v];

            s.push(v);

            parcurgere(v);

            llk[ind]=min(llk[ind],llk[v]);

            if (llk[v]>=ix[ind])

            {

                //rez[k].resize(0);

                while (s.top()!=v)

                {

                    rez[k].push_back(s.top());

                    s.pop();

                }

                rez[k].push_back(s.top());

                s.pop();

                rez[k].push_back(ind);

                k++;



            }



        }

        else if (viz[v])

        {

            llk[ind]=min(llk[ind],ix[v]);

        }

    }

}



int main()

{

    citire();

    for (int i=1; i<=n; ++i)

    {

        if (!viz[i])

        {

            parcurgere(i);

        }

    }

    g << k << '\n';

    for (int i=0; i<k; ++i)

    {

        for (auto &v:rez[i])

        {

            g << v <<' ';

        }

        g << '\n';

    }

    return 0;

}