Cod sursa(job #1155864)

Utilizator vlad008Stan Vladut Angel vlad008 Data 27 martie 2014 11:19:34
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<iostream>
#define N 100100
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
ifstream f("intrare.in");
ofstream g("biconex.out");
vector<int> b[N],v[N];
stack<pair<int,int> > st;
int i,n,m,x,y,cb,low[N],niv[N],t,j;
void dfs(int nod,int pr)
{
    ++t;
    low[nod]=niv[nod]=t;
    for(int i=0;i<v[nod].size();++i)
        if(v[nod][i]!=pr)
        {
            if(!niv[v[nod][i]])
            {
                st.push(make_pair(nod,v[nod][i]));
                dfs(v[nod][i],nod);
                if(low[v[nod][i]]>=niv[nod])
                {
                    int x,y;
                    ++cb;
                    do
                    {
                        x=st.top().first;
                        y=st.top().second;
                        b[cb].push_back(y);
                        st.pop();
                    }
                    while(x!=nod&&y!=v[nod][i]);
                    b[cb].push_back(nod);
                }
            }
            low[nod]=min(low[nod],low[v[nod][i]]);
        }
    --t;
}
int main ()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,-1);
    cout<<cb<<"\n";
    for(i=1;i<=cb;++i)
    {
        for(j=0;j<b[i].size();++j)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}