Cod sursa(job #1435922)

Utilizator sorynsooSorin Soo sorynsoo Data 14 mai 2015 19:30:42
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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)
{
    int x=st.top();
    do
    {
        int urm=st.top();  st.pop();
        rasp[cbc].push_back(urm);
    }while(st.top()!=nod);
    rasp[cbc].push_back(nod);
}
void dfs(int nod, int tata, 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,nod,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,0,1);
   cout<<cbc<<"\n";
   for(i=1; i<=cbc; i++)
   {
       for(j=0; j<rasp[i].size(); j++)
        cout<<rasp[i][j]<<" ";
       cout<<"\n";
   }
}