Cod sursa(job #1141552)

Utilizator Lucian-GeorgeFMI Popa Lucian George Lucian-George Data 12 martie 2014 22:49:17
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
  
int i,j,n,m,niv[20001],c[20001],viz[20001],r1[20001],r2[200001],x,y,verge=0,nr=0;
vector<int> v[20001];
vector<int> sol[20001];

void add(int a,int b){
	int x,y;
	++nr;
    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 (std::vector<int>::iterator it=v[nod].begin(); it!=v[nod].end(); ++it){
        int x=*it;
        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 () 
{
	ifstream f("biconex.in");
	ofstream g("biconex.out");
    f>>n>>m;
  
    for(i=1;i<=m;++i){
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
	
    dfs(1,0);
    g<<nr<<"\n";
    for(i=1;i<=nr;++i){
		for(std::vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); ++it){
            g<<*it<<" ";
        }
        g<<"\n";
    }
    return 0;
}