Cod sursa(job #2246191)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 26 septembrie 2018 19:34:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#define nmax  100002
using namespace std;
fstream f1("biconex.in", ios::in);
fstream f2("biconex.out", ios::out);
int nrcomp, n, m, niv[nmax], low[nmax];
vector<int> v[nmax], q;
vector<vector<int> > comp;
///low[nod]=min(niv[nod], low["fiu" nod nevizitat], niv["fiu" nod vizitat])
void dfs(int nod, int tata, int nivel){

    niv[nod]=low[nod]=nivel;
    q.push_back(nod);
    for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        if(*it!=tata){
           if(niv[*it]) low[nod]=min(low[nod], niv[*it]);
           else {dfs(*it, nod, nivel+1); low[nod]=min(low[nod], low[*it]);}
    }

    if((nod!=1)&&(low[nod]>=niv[tata])){ //tata este punct de articulatie, pui in noua comp nod, toate nodurile neluate de sub el+ tata
       nrcomp++; vector<int> ceva; ceva.clear();
       while((!q.empty())&&(q.back()!=nod)){
           ceva.push_back(q.back()); q.pop_back();
       }
        ceva.push_back(q.back()); q.pop_back();
        ceva.push_back(tata); /// sau q.back()
        comp.push_back(ceva);
    }
}
int main(){

    int x, y;
    f1>>n>>m;
    for(int i=1; i<=m; i++){
        f1>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, -1, 1);
    f2<<nrcomp<<"\n";
    for(auto it2=comp.begin(); it2!=comp.end() ;++it2){
        for(auto it=(*it2).begin(); it!=(*it2).end(); ++it)
            f2<<*it<<' ';
        f2<<"\n";
    }
    return 0;
}