Cod sursa(job #2135121)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 18 februarie 2018 16:52:13
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <deque>
#define DIM 100002
#define f first
#define s second

using namespace std;

ifstream in ("biconex.in");
ofstream out("biconex.out");

int n, x, y, tip, m, low[DIM], lvl[DIM], nr1;

bool viz[DIM];

vector<int> graf[DIM];

deque<pair<int, int> > q;

vector<vector<int> > cb;

void get_cb(int nod, int nodc){
    vector<int> newCB;
    while(q.back().f != nod && q.back().s != nodc){
        newCB.push_back(q.back().s);
        q.pop_back();
    }
    newCB.push_back(q.back().f);
    newCB.push_back(q.back().s);
    q.pop_back();
    cb.push_back(newCB);
}

void dfs(int nod, int niv, int tata){
    viz[nod] = 1;
    low[nod] = lvl[nod] = niv;
    for(int i = 0; i < graf[nod].size(); ++ i){
        int nodc = graf[nod][i];
        if(nodc == tata) continue;
        if(!viz[nodc]){
            q.push_back(make_pair(nod, nodc));
            dfs(nodc, niv + 1, nod);
            low[nod] = min(low[nod], low[nodc]);
            if(low[nodc] >= lvl[nod])
                get_cb(nod, nodc);
        }
        else
            low[nod] = min(low[nod], lvl[nodc]);
    }
}

void afis_cb(){
    out<<cb.size()<<'\n';
    for(int i = 0; i < cb.size(); ++ i){
        for(int j = 0; j < cb[i].size(); ++ j)
            out<<cb[i][j]<<" ";
        out<<'\n';
    }
}

int main() {
    tip = 1;
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i = 0; i <= n + 1; ++ i)
        lvl[i] = -1;
    dfs(1, 0, 0);
    afis_cb();
    return 0;
}