Cod sursa(job #2323618)

Utilizator Cristian.BBurghelea Cristian Cristian.B Data 19 ianuarie 2019 14:06:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int>v[100005];
vector<int>comp[100005];
int nivel[100005],nma[100005],n,x,y,m,nrpnt,nrcomp;
bool viz[100005],pda[100005];
stack<int>s;

//struct punte{int x,y;}pnt[100005];

void DFS(int k, int tata)
{
    viz[k]=true;
    s.push(k);
    nivel[k]=nivel[tata]+1;
    nma[k]=nivel[k];
    for(vector<int>::iterator i=v[k].begin();i!=v[k].end();++i){
        int x=*i;
        if(x != tata)
            if(viz[x])nma[k]=min(nma[k],nivel[x]);
            else{
               DFS(x,k);
               nma[k]=min(nma[k],nma[x]);

               ///PUNCTE DE ARTICULATIE
               //if(nivel[k]<=nma[x] && k!=1)pda[k]=true;

               ///PUNTI
              // if(nivel[k]<nma[x]){pnt[++nrpnt].x=k; pnt[nrpnt].y=x;}

               ///COMPONENTE BICONEXE
               if(nivel[k]<=nma[x]){
                    ++nrcomp;
                    while(s.top()!=x){
                        comp[nrcomp].push_back(s.top());
                        s.pop();
                    }
                    comp[nrcomp].push_back(x);
                    s.pop();
                    comp[nrcomp].push_back(k);
               }
            }

    }
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;++i){
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1,0);

    /*fout<<"Puncte de articulatie:"<<'\n';
    for(int i=1;i<=n;++i)if(pda[i])fout<<i<<' ';
    fout<<'\n'<<'\n'<<"Punti:"<<'\n';
    for(int i=1;i<=nrpnt;++i)fout<<pnt[i].x<<'-'<<pnt[i].y<<'\n';*/

    fout<<nrcomp<<'\n';
    for(int i=1;i<=nrcomp;++i){
        for(vector<int>::iterator j=comp[i].begin();j!=comp[i].end();++j)
            fout<<*j<<' ';
        fout<<'\n';
    }

    fin.close(); fout.close();
    return 0;
}