Cod sursa(job #2599587)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 11 aprilie 2020 15:09:22
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

const int MAXN = 200001;

using namespace std;

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

vector<int>graf[MAXN];
vector<pair<int,int>>stiva;
int n,m,inaltime[MAXN],minim[MAXN];
int nr_comp,cnt = 1;
vector<int>componente[MAXN];
bool viz[MAXN];

void biconexa(int x,int y){
    nr_comp++;

    while(stiva.back() != make_pair(x,y)){
        int nod1 = stiva.back().first,nod2 = stiva.back().second;
        componente[nr_comp].push_back(nod1);
        componente[nr_comp].push_back(nod2);
        stiva.pop_back();
    }
    componente[nr_comp].push_back(x);
    componente[nr_comp].push_back(y);
    stiva.pop_back();
}
void afis(){
    for(int i = 1; i <= n; i++)
        cout<<minim[i]<<" ";
    cout<<endl;
}
void dfs(int nod,int tata = 0){
    viz[nod] = true;
//    cout<<"Fata"<<"\n";
//    afis();
    for(auto vecin : graf[nod]){
        if(viz[vecin] && vecin != tata && inaltime[vecin] < inaltime[nod]){
            stiva.emplace_back(nod,vecin);
            /// ma duc sus pe graf
            minim[nod] = min(minim[nod],minim[vecin]);
        }else if(!viz[vecin]){
            inaltime[vecin] = ++cnt;
            minim[vecin] = inaltime[vecin];
            stiva.emplace_back(nod,vecin);
            dfs(vecin,nod);
        }
    }
    if(tata != 0 && minim[nod] >= inaltime[tata]){
//        cout<<tata<<" "<<nod<<"tata nod\n";
//        for(auto muchie : stiva)
//            cout<<muchie.first<<" "<<muchie.second<<"\n";
        biconexa(tata,nod);
    }
    if(minim[nod] < minim[tata])
        minim[tata] = minim[nod];
//    cout<<"Inapoi"<<"\n";
//    afis();
}


int main()
{
    in>>n>>m;

    for(int i = 1; i <= m; i++){
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    inaltime[1] = minim[1] = 1;
    dfs(1);

    out<<nr_comp<<"\n";
    for(int i = 1; i <= nr_comp; i++){
        sort(componente[i].begin(),componente[i].end());
        componente[i].erase(unique(componente[i].begin(),componente[i].end()),componente[i].end());
        for(auto nod : componente[i])
            out<<nod<<" ";
        out<<"\n";
    }
    return 0;
}