Cod sursa(job #2372561)

Utilizator WayronUrsu Ianis-Vlad Wayron Data 7 martie 2019 09:55:06
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <vector>
#include <fstream>
#include <stack>
#define NMAX 100001
#define MMAX 200001

using namespace std;

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

int low[NMAX], level[NMAX], step = 0;
vector<vector<int>> graph = vector<vector<int>>(NMAX, vector<int>());
vector<vector<int>> rasp;

stack<int> stiva;
void biconex(int nod){
    step++;
    low[nod] = level[nod] = step;
    stiva.push(nod);

    for(auto& copil:graph[nod]){
        if(level[copil]){
            low[nod] = min(low[nod], level[copil]); continue;
        }
        biconex(copil);
        low[nod] = min(low[nod], low[copil]);

        if(low[copil]>=level[nod]){
            vector<int> c;
            while(stiva.top()!=copil){
                c.push_back(stiva.top());
                stiva.pop();
            }

            stiva.pop();
            c.push_back(copil);
            c.push_back(nod);

            rasp.push_back(c);
        }
    }
}
int main()
{
    int n, m, x, y;
    fin>>n>>m;

    for(int i=1; i<=m; i++){
        fin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    biconex(1);
    fout<<rasp.size()<<endl;

    for(auto& c:rasp){
        for(auto& nod:c) fout<<nod<<" ";
        fout<<endl;
    }
}