Cod sursa(job #729839)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 30 martie 2012 12:42:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100002

using namespace std;

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

vector<int> V[nmax];
vector<int> Sol[nmax];
stack<pair<int,int> > S;

int N,M,K;
int Intoarcere[nmax],Nivel[nmax],T[nmax],Atinge;

inline int _min(int a,int b){if(a<b)return a;return b;}

inline void Adauga(int nod,int tata)
{
    int a,b;
    for(;a!=nod&&b!=tata;)
    {
        a = S.top().first;
        b = S.top().second;
        S.pop();
        Sol[K].push_back(a);
    }
    Sol[K].push_back(tata);
    K++;
}

void DFS(int nod)
{
    int y,i;
    Intoarcere[nod] = Nivel[nod];
    for(i=0;i<V[nod].size();i++)
    {
        y = V[nod][i];
        if(!Nivel[y])
        {
            T[y] = nod;
            S.push(make_pair(y,nod));
            Nivel[y] = Nivel[nod]+1;
            if(y==1)
                Atinge++;
            DFS(y);
            Intoarcere[nod]=_min(Intoarcere[nod],Intoarcere[y]);
            if(Intoarcere[y]>=Nivel[nod])//nu pot ajunge mai sus in arbore->nod critic
                Adauga(y,nod);
        }
        else if(y!=T[nod])
            Intoarcere[nod]=_min(Intoarcere[nod],Nivel[y]);
    }
}

int main()
{
    int x,y;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y;
        V[x].push_back(y),V[y].push_back(x);
    }
    Nivel[1] = 1;
    DFS(1);
    out<<K<<'\n';
    for(x=0;x<K;x++)
    {
        for(y=0;y<Sol[x].size();y++)
            out<<Sol[x][y]<<' ';
        out<<'\n';
    }
    return 0;
}