Cod sursa(job #2498872)

Utilizator Raresr14Rosca Rares Raresr14 Data 24 noiembrie 2019 18:08:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <stack>
#include <vector>
#define DIM 100010
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,i,j,x,y,f[DIM],low[DIM],Niv[DIM],comp;
stack<int> ST;
vector<int> L[DIM],C[DIM];
void dfs(int nod, int tata, int niv){
    f[nod]=1;
    Niv[nod]=low[nod]=niv;
    ST.push(nod);
    for(int i=0;i<L[nod].size();i++){
        int vec=L[nod][i];
        if(f[vec]==1){
            low[nod]=min(low[nod],Niv[vec]);
        }else{
            dfs(vec,nod,niv+1);
            low[nod]=min(low[nod],low[vec]);
            if(low[vec]>=Niv[nod]){
                comp++;
                do{
                    x=ST.top();
                    C[comp].push_back(x);
                    ST.pop();
                }while(x!=vec);
                C[comp].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,0,1);
    fout<<comp<<"\n";
    for(i=1;i<=comp;i++){
        for(j=0;j<C[i].size();j++)
            fout<<C[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}