Cod sursa(job #2571877)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 5 martie 2020 10:35:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
#define NMAX 100009
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[NMAX];
int n,m;
void dfs(int k, int tata);
stack<int>s;
int nma[NMAX];
int lvl[NMAX];
bool uz[NMAX];
vector<int>sol[NMAX];
int nrsol;
void citire();
void afis();
int main()
{citire();
 dfs(1,0);
 afis();
    return 0;
}
void citire()
{
 int i;
 int x,y;
 fin>>n>>m;
 for(i=1;i<=m;i++)
    {
     fin>>x>>y;
     g[x].push_back(y);
     g[y].push_back(x);
    }
}
void dfs(int k, int tata)
{int i;
  uz[k]=1;
  nma[k]=lvl[k]=lvl[tata]+1;
  s.push(k);
   for  (i=0;i<g[k].size();i++)
        {
         int act=g[k][i];
         if(uz[act])
            {
             if(nma[k]> lvl[act])
                nma[k]=lvl[act];
            }
            else
            {
             dfs(act,k);
             if(nma[act]<nma[k])
                    nma[k]=nma[act];
             if(nma[act]>=lvl[k])
                {
                 while(s.top()!=act)
                    {
                     sol[nrsol].push_back(s.top());s.pop();
                    }
                  s.pop();
                  sol[nrsol].push_back(k);
                  sol[nrsol].push_back( act);
                  nrsol++;
                }
            }
        }
}

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