Cod sursa(job #2595233)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 7 aprilie 2020 13:17:38
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

const int MAXN = 100001;

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 dfs(int nod,int tata = 0){
    viz[nod] = true;
    for(auto vecin : graf[nod]){
        if(vecin != tata && inaltime[vecin] < inaltime[nod])
            stiva.emplace_back(nod,vecin);
        if(viz[vecin] && vecin != tata && inaltime[vecin] < inaltime[nod]){
            /// ma duc sus pe graf
            minim[nod] = minim[vecin];
        }else if(!viz[vecin]){
            inaltime[vecin] = ++cnt;
            minim[vecin] = inaltime[vecin];
            dfs(vecin,nod);
        }
    }

    if(minim[nod] >= minim[tata] && tata){
//        cout<<tata<<" "<<nod<<endl;
//        cout<<"stiva : "<<"\n";
//        for(int i = stiva.size() - 1; i >= 0; i--)
//            cout<<stiva[i].first<<" "<<stiva[i].second<<"\n";
//        cout<<"======="<<"\n";
        biconexa(tata,nod);
    }
    //cout<<tata<<" "<<nod<<" "<<minim[tata]<<" "<<minim[nod]<<endl;
    if(minim[nod] < minim[tata])
        minim[tata] = minim[nod];

}

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);
//    for(int i = 1; i <= n; i++)
//        cout<<minim[i]<<" ";
    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;
}