Cod sursa(job #1032898)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 16 noiembrie 2013 10:42:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define minim(a,b) (a<b?a:b)
#define DIM 100011
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr;
int viz[DIM],low[DIM];

set<int> sol[DIM];
set<int>::iterator it;
vector<int> L[DIM];
stack<pair<int,int> > S;


void extract(int x,int y){
    int tx,ty;
    nr++;
    do{
        tx=S.top().first,ty=S.top().second;
        sol[nr].insert(tx),sol[nr].insert(ty);
        S.pop();
    }while((tx!=x || ty!=y) && !S.empty());
    sol[nr].insert(ty),sol[nr].insert(tx);
}

void dfs(int nod,int k,int fn){
    viz[nod]=low[nod]=k;
    S.push(make_pair(fn,nod));
    for(register int i=0;i<L[nod].size();i++){
        if(!viz[L[nod][i]]){
            dfs(L[nod][i],k+1,nod);
            low[nod]=minim(low[nod],low[L[nod][i]]);
            if(low[L[nod][i]]>=viz[nod])
                 extract(nod,L[nod][i]);
        }
        else
            low[nod]=minim(low[nod],viz[L[nod][i]]);
    }
}

int main(void){

    register int i,j,x,y;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    dfs(1,1,0);

    g<<nr<<"\n";
    for(i=1;i<=nr;i++){
        for(it=sol[i].begin();it!=sol[i].end();it++)
            g<<*it<<" ";
        g<<"\n";
    }

    f.close();
    g.close();
    return 0;
}