Cod sursa(job #701088)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 1 martie 2012 13:33:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100005

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 Intoarcere[nmax],T[nmax],Nivel[nmax],Atinge;
int N,M,nr;
int cr,r1[nmax],r2[nmax];

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

void Add(int x,int nod)
{
    int a,b;
    do
    {
        a=S.top().first,b=S.top().second;
        S.pop();
        Sol[nr].push_back(a);
    }
    while(a!=x||b!=nod);
    Sol[nr].push_back(nod);
    nr++;
}

/*void Add(int a,int b)
{
    int x,y;
    do
    {
        x=r1[cr];
        y=r2[cr--];
        Sol[nr].push_back(y);
    }while(x!=a||y!=b);
    Sol[nr].push_back(x);
    nr++;
}*/

void DFS(int nod)
{
    int i,x;
    Intoarcere[nod] = Nivel[nod];
    for(i=0;i<V[nod].size();i++)
    {
        x = V[nod][i];
        if(!Nivel[x])//nu a fost parcurs
        {
            T[x] = nod;
            S.push(make_pair(x,nod));
           // r1[++cr]=nod;
           // r2[cr]=x;
            Nivel[x] = Nivel[nod]+1;
            if(nod==1)Atinge++;
            DFS(x);
            Intoarcere[nod]=_min(Intoarcere[nod],Intoarcere[x]);
            if(Intoarcere[x]>=Nivel[nod])//nu pot ajunge mai sus deci nod e critic
                Add(x,nod);
        }
        else if(x!=T[nod])
            Intoarcere[nod]=_min(Intoarcere[nod],Nivel[x]);
    }
}

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