Cod sursa(job #2564090)

Utilizator valentin12Valentin Ion Semen valentin12 Data 1 martie 2020 17:44:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#define DIM 100010

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int v[DIM],NIV[DIM],LOW[DIM];
int componente,n,m,x,y,p,i,j,k;
stack <int> ST;
vector <int> L[DIM],C[DIM];



void dfs(int nod,int tata,int niv)
{
v[nod]=1;
NIV[nod]=niv;
LOW[nod]=niv;
ST.push(nod);
for(int i=0;i<L[nod].size();i++)
{
int vecin=L[nod][i];
if(vecin==tata) continue;
if(v[vecin]) LOW[nod]=min(LOW[nod],NIV[vecin]);
else
{
dfs(vecin,nod,niv+1);
LOW[nod]=min(LOW[nod],LOW[vecin]);
if(LOW[vecin]>=NIV[nod])
{
componente++;
do
{
x=ST.top();
C[componente].push_back(x);
ST.pop();
}
while(x!=vecin);
C[componente].push_back(nod);
}

}
}

}

int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs(1,0,1);
g<<componente<<'\n';
for(i=1;i<=componente;i++)
{
for(j=0;j<C[i].size();j++)
g<<C[i][j]<<" ";
g<<'\n';
}


    return 0;
}