Cod sursa(job #2488248)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 6 noiembrie 2019 16:06:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <deque>
#include <vector>
#define dim 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int nivel[dim],low[dim],t[dim],nrcomp,n,m,x,y,i;
bitset <dim> fr;
deque<int> q;
vector <int> L[dim];
vector <int> C[dim];
void dfs(int nod,int niv,int tata){
nivel[nod]=niv;
low[nod]=niv;
t[nod]=tata;
q.push_back(nod);
    for(int i=0;i<L[nod].size();i++){
        int vecin=L[nod][i];
        if(vecin==tata)
        continue;
        if(fr[vecin]==1){
            low[nod]=min(low[nod],nivel[vecin]);
            continue;
        }
        fr[vecin]=1;
        dfs(vecin,niv+1,nod);
            low[nod]=min(low[nod],low[vecin]);
        if(low[vecin]>=nivel[nod]){
            nrcomp++;
            while(q.back()!=vecin){
                C[nrcomp].push_back(q.back());
                q.pop_back();
            }
            C[nrcomp].push_back(vecin);q.pop_back();
            C[nrcomp].push_back(nod);
        }
    }
}
int main()
{
   fin>>n>>m;
   for(i=1;i<=m;i++){
    fin>>x>>y;
    L[x].push_back(y);
    L[y].push_back(x);
   }
   dfs(1,1,0);
   fout<<nrcomp<<"\n";
   for(i=1;i<=n;i++){
    for(int j=0;j<C[i].size();j++)
        fout<<C[i][j]<<" ";
    fout<<"\n";
       }
}