Cod sursa(job #2651878)

Utilizator LeCapataIustinian Serban LeCapata Data 23 septembrie 2020 18:50:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
#define N 100005
using namespace std;

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

int n, m;
bool vizitat[N];
int lowestLevel[N], level[N];
vector<vector<int> > graf(N), solutie;

stack<int> stiva;

struct grafNod{
    int x, tata;
};

queue<grafNod> coada;

void adauga(grafNod nod){
    vector<int> crt;
    while(stiva.top() != nod.x){
        crt.push_back(stiva.top());
        stiva.pop();
    }
    stiva.pop();

    crt.push_back(nod.x);
    crt.push_back(nod.tata);

    solutie.push_back(crt);
}

void dfs(){
    grafNod nod = coada.front();
    coada.pop();
    vizitat[nod.x] = true;

    for(size_t i = 0; i < graf[nod.x].size(); ++i){
        if(graf[nod.x][i] == nod.tata) continue;
        if(vizitat[graf[nod.x][i]]) lowestLevel[nod.x] = min(lowestLevel[nod.x], level[graf[nod.x][i]]);
        else{
            stiva.push(graf[nod.x][i]);
            level[graf[nod.x][i]] = level[nod.x] + 1;

            grafNod nod2;
            nod2.x = graf[nod.x][i];
            nod2.tata = nod.x;
            coada.push(nod2);
            dfs();

            lowestLevel[nod.x] = min(lowestLevel[nod.x], lowestLevel[graf[nod.x][i]]);

            if(level[nod.x] <= lowestLevel[graf[nod.x][i]])
                adauga(nod2);
        }
    }
}

int main()
{
    in>>n>>m;
    while(m--){
        int x, y;
        in>>x>>y;

        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    memset(lowestLevel, 0x3f, sizeof lowestLevel);
    for(int i = 1; i <= n; ++i)
    if(!vizitat[i]){
        grafNod nod;
        nod.x = i; nod.tata = 0;
        coada.push(nod);
        dfs();
    }

    out<<solutie.size()<<'\n';
    for(size_t i = 0; i < solutie.size(); ++i){
        for(size_t j = 0; j < solutie[i].size(); ++j)
            out<<solutie[i][j]<<" ";
        out<<'\n';
    }

    in.close();
    out.close();
    return 0;
}