Cod sursa(job #2396528)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 3 aprilie 2019 16:39:16
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001
using namespace std;
ifstream f1("biconex.in");
ofstream f2("biconex.out");

vector<int> sol[NMAX], v[NMAX];
stack<int> staci;
int n,m,nivel[NMAX],amTrecutPeAici[NMAX], drumIntoarcere[NMAX];
int nrNodDeMijloc;
void dfs(int fiu, int tata){
    nivel[fiu] = nivel[tata]+1;
    amTrecutPeAici[fiu]=1;
    staci.push(fiu);
    drumIntoarcere[fiu] = nivel[fiu];
    for(auto x : v[fiu]){
        if(x == tata) continue;
        if(amTrecutPeAici[x]==1){
            drumIntoarcere[fiu] = nivel[x]<drumIntoarcere[fiu] ? nivel[x] : drumIntoarcere[fiu];
            continue;
        }
        dfs(x,fiu);
        drumIntoarcere[fiu] = drumIntoarcere[x]<drumIntoarcere[fiu] ? drumIntoarcere[x] : drumIntoarcere[fiu];
        if(nivel[fiu]<=drumIntoarcere[x]){
            ++nrNodDeMijloc;
            int t;
            do{
                t = staci.top();
                staci.pop();
                sol[nrNodDeMijloc].push_back(t);
            }while(!staci.empty() && t!=x);
            sol[nrNodDeMijloc].push_back(fiu);
        }
    }
}

int main() {
    f1>>n>>m;
    int a,b;
    for(int i=0;i<m;i++){
        f1>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    f2<<nrNodDeMijloc<<"\n";
    for(int i=1;i<=nrNodDeMijloc;i++){
        for(auto x : sol[i]){
            f2<<x<<" ";
        }
        f2<<"\n";
    };
    return 0;
}