Cod sursa(job #2128949)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 12 februarie 2018 12:25:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#define DIM 100002
#define f first
#define s second

using namespace std;

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

int n, m, x, y, art[DIM], viz[DIM], nivmin[DIM], lvl[DIM];

vector <int> graf[DIM];
vector <vector<int> > cc;
deque <pair<int, int> > q;

void make_cc(int x, int y){
    vector <int> v;
    while(q.back().f != x || q.back().s != y){
        v.push_back(q.back().f);
        v.push_back(q.back().s);
        q.pop_back();
    }
    v.push_back(x);
    v.push_back(y);
    q.pop_back();
    cc.push_back(v);
}

void dfs(int nod, int tata, int niv){
    viz[nod] = 1;
    nivmin[nod] = niv;
    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, nod, niv + 1);
            nivmin[nod] = min(nivmin[nodc], nivmin[nod]);
            if(nivmin[nodc] >= lvl[nod]){
                make_cc(nod, nodc);
            }
        }
        else
            nivmin[nod] = min(nivmin[nod], lvl[nodc]);
    }
}

int main() {
    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);
    out<<cc.size()<<'\n';
    for(int i = 0; i < cc.size(); ++ i){
        sort(cc[i].begin(), cc[i].end());
        cc[i].erase(unique(cc[i].begin(), cc[i].end()), cc[i].end());
        for(int j = 0; j < cc[i].size(); ++ j){
            out<<cc[i][j]<<" ";
        }
        out<<'\n';
    }
    return 0;
}