Cod sursa(job #2135039)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 18 februarie 2018 15:54:36
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <vector>
#define DIM 1000002

using namespace std;

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

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

bool viz[DIM];

vector<int> graf[DIM], q;

vector<vector<int> > cb;

void get_cb(int nod){
    vector<int> newCB;
    while(q.back() != nod){
        newCB.push_back(q.back());
       // ++ art_nod[q.back()];
        q.pop_back();
    }
    newCB.push_back(q.back());
   // ++ art_nod[q.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(nodc);
            dfs(nodc, niv + 1, nod);
            low[nod] = min(low[nod], low[nodc]);
            if(low[nodc] >= lvl[nod])
                get_cb(nod);
        }
        else
            low[nod] = min(low[nod], lvl[nodc]);
    }
}

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

//void afis_nodes(){
//    int nr = 0;
//    for(int i = 1; i <= n; ++ i)
//        if(art_nod[i] > 1)
//            ++ nr;
//    out<<nr<<'\n';
//    for(int i = 1; i <= n; ++ i)
//        if(art_nod[i] > 1)
//            out<<i<<" ";
//}

//void afis_edges(){
//    int nr = 0;
//    for(int i = 0; i < cb.size(); ++ i)
//        if(cb[i].size() == 2)
//            ++ nr;
//    out<<nr<<'\n';
//    for(int i = 0; i < cb.size(); ++ i)
//        if(cb[i].size() == 2)
//            out<<cb[i][0]<<" "<<cb[i][1]<<'\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);
    }
    q.push_back(1);
    dfs(1, 0, 0);
//    switch(tip){
//        case 1:afis_cb();    break;
//        case 2:afis_nodes(); break;
//        case 3:afis_edges(); break;
//    }
    afis_cb();
    return 0;
}