Cod sursa(job #1540755)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 3 decembrie 2015 10:38:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<vector>
#include<deque>
#define DIM 100005
using namespace std;
int n, m, i, x, y, nr, j;
int niv[DIM], low[DIM], viz[DIM];
deque<int> c;
vector<int> v[DIM], sol[DIM];
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void dfs(int nod, int tata){
    viz[nod] = 1;
    niv[nod] = niv[tata] + 1;
    low[nod] = niv[nod];
    c.push_back(nod);
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(vecin == tata){
            continue;
        }
        if(viz[vecin] == 1){
            low[nod] = min(low[nod], niv[vecin]);
        }
        else{
            dfs(vecin, nod);
            low[nod] = min(low[nod], low[vecin]);
            if(low[vecin] >= niv[nod]){
                nr++;
                sol[nr].push_back(nod);
                int x;
                do{
                    sol[nr].push_back( c.back() );
                    x = c.back();
                    c.pop_back();
                }while(x != vecin);
            }
        }
    }
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    fout<< nr <<"\n";
    for(i = 1; i <= nr; i++){
        for(j = 0; j < sol[i].size(); j++){
            fout<< sol[i][j] <<" ";
        }
        fout<<"\n";
    }
    return 0;
}