Mai intai trebuie sa te autentifici.

Cod sursa(job #901040)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 28 februarie 2013 23:46:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<vector>
#define nmax 200001
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");
int i,j,n,m,niv[nmax],c[nmax],viz[nmax],r1[nmax],r2[nmax],x,y,verge=0,nr=0;
vector<int> G[nmax];
vector<int> sol[nmax];
void add(int a,int b) {
    ++nr;
int x,y;
    do{
        x=r1[verge];
        y=r2[verge--];
        sol[nr].push_back(y);
    }while(x!=a || y!=b);

    sol[nr].push_back(x);
}
void dfs(int nod,int tata){
    niv[nod]=niv[tata]+1;
    c[nod]=niv[nod];

    viz[nod]=1;

    for(int i=0;i<G[nod].size();++i){
        int x=G[nod][i];
        if(!viz[x]) {
            r1[++verge]=nod;
            r2[verge]=x;
            dfs(x,nod);
            if(c[x]<c[nod])
                c[nod]=c[x];
            if(c[x]>=niv[nod])
                add(nod,x);
        }
        else{
            if(x!=tata && c[x]<c[nod])
                c[nod]=c[x];
        }
    }
}
int main () {
    f>>n>>m;

    for(i=1;i<=m;++i){

        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);

    }
    dfs(1,0);
    g<<nr<<"\n";
    for(i=1;i<=nr;++i){

        for(j=0;j<sol[i].size();++j){
            g<<sol[i][j]<<" ";
        }
        g<<"\n";
    }
    return 0;

}