Cod sursa(job #2266002)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 22 octombrie 2018 00:00:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define NMAX 100001
#define mp make_pair
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int query, n, m, d[NMAX], low[NMAX], step = 1, ans2,mod;
vector <int> v[NMAX];

vector < vector <int> > sol;
stack <int> st;

bool check[NMAX], articulatie[NMAX];

void DFS(int nod, int last)
{


    check[nod] = true;
    d[nod] = low[nod] = step++;
    st.push(nod);
     for(int i = 0; i < v[nod].size(); i++)
     {
         int nod_urm = v[nod][i];

         if(nod_urm != last)
         {

             if(check[nod_urm])
             {
                 low[nod] = min(low[nod], d[nod_urm]);
                 continue;
             }
             DFS(nod_urm, nod);
             low[nod] = min(low[nod], low[nod_urm]);

                if(low[nod_urm] >= d[nod]){
                vector <int> ad;
                while(st.top() != nod_urm){
                ad.push_back(st.top());
                st.pop();
                }
                st.pop();
                ad.push_back(nod_urm);
                ad.push_back(nod);
                sol.push_back(ad);
             }
         }

     }







}

int main()
{

    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);

    }

    DFS(1, 0);

            fout << sol.size() << '\n';
            for(int i = 0; i < sol.size(); i++)
            {

                for(int j = 0; j < sol[i].size(); j++)
                    fout << sol[i][j] << " ";
                fout << '\n';
            }




    return 0;
}