Cod sursa(job #1609953)

Utilizator sorynsooSorin Soo sorynsoo Data 23 februarie 2016 10:25:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector<int> graf[100001],rasp[100001];
stack<int> st;
int nivel[100001],low[100001];
int n,m,i,j,x,y,cbc;

void scoate(int nod, int next)
{

      while(st.top() != next)
      {
          rasp[cbc].push_back(st.top());
          st.pop();
      }
    st.pop();
    rasp[cbc].push_back(nod);
    rasp[cbc].push_back(next);
}
void dfs(int nod, int k)
{
    nivel[nod]=low[nod]=k;
    for(int i=0; i<graf[nod].size(); i++)
    {
        int next=graf[nod][i];
        if(!nivel[next])
        {
            st.push(next);
            dfs(next,k+1);
            low[nod]=min(low[nod],low[next]);
            if(low[next]>=nivel[nod])
            {
                cbc++;
                scoate(nod,next);
            }
        }
        else
            low[nod]=min(low[nod],nivel[next]);
    }
}

int main()
{
   cin>>n>>m;
   for(i=1; i<=m; i++)
   {
       cin>>x>>y;
       graf[x].push_back(y);
       graf[y].push_back(x);
   }
   st.push(1);
   dfs(1,1);
   cout<<cbc<<"\n";
   for(i=1; i<=cbc; i++)
   {
       for(j=0; j<rasp[i].size(); j++)
        cout<<rasp[i][j]<<" ";
       cout<<"\n";
   }
}