Cod sursa(job #1112050)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 19 februarie 2014 13:03:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

stack <pair <int,int> > Stack;
vector <int> v[100010],sol[100010];
int N,M,nrsol,nivel[100010],adn[100010];

void citire() {

    ifstream in("biconex.in");
    int i,x,y;
    in>>N>>M;
    for(i=1;i<=M;i++) {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();

}

void dfs(int nod,int tata) {

    int i,vecin,x,y;
    nivel[nod]=nivel[tata]+1;
    adn[nod]=nivel[nod];
    for(i=0;i<v[nod].size();i++) {
        vecin=v[nod][i];
        if(vecin!=tata) {
            if(nivel[vecin]==0){
                Stack.push(make_pair(nod,vecin));
                dfs(vecin,nod);
                if(adn[vecin]>=nivel[nod]) {
                    nrsol++;
                    x=Stack.top().first;
                    y=Stack.top().second;
                    sol[nrsol].push_back(y);
                    Stack.pop();
                    while(nod!=x && vecin!=y) {
                        x=Stack.top().first;
                        y=Stack.top().second;
                        sol[nrsol].push_back(y);
                        Stack.pop();
                    }
                    sol[nrsol].push_back(x);

                }
            }
        adn[nod]=min(adn[nod],adn[vecin]);
        }
    }

}

void afisare() {

    ofstream out("biconex.out");
    int i,j;
    out<<nrsol<<'\n';
    for(i=1;i<=nrsol;i++) {
        for(j=0;j<sol[i].size();j++)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
    out.close();

}

int main() {

    citire();
    dfs(1,0);
    afisare();
    return 0;

}