Cod sursa(job #3151466)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 21 septembrie 2023 15:02:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
struct ura
{
vector <int> l;
int niv,nivm;
}g[100001];
int vf[100001],nr,st[100001],p;
vector <vector<int>> rez;
vector <int> v;
void dfs(int k, int t)
{
if(t==1)
nr++;
vf[k]=1;
st[++p]=k;
g[k].niv=g[t].niv+1;
g[k].nivm=g[k].niv;
int ok=0;
for(size_t i=0;i<g[k].l.size();i++)
{
if(vf[g[k].l[i]]==0)///fiu
{
dfs(g[k].l[i],k);
g[k].nivm=min(g[k].nivm,g[g[k].l[i]].nivm);
if(g[k].niv<=g[g[k].l[i]].nivm)///punct de articulatie
{
ok=1;
vector <int> v;///componenta biconexa
while(st[p]!=g[k].l[i])
{
v.push_back(st[p]);
p--;
}
v.push_back(g[k].l[i]);
v.push_back(k);
rez.push_back(v);
p--;
}
if(g[k].niv<g[g[k].l[i]].nivm);///punte
///cout<<k<<" "<<g[k].l[i]<<" punte"<<'\n';
}
else
if(g[k].l[i]!=t)///muchie de intoarcere
{
g[k].nivm=min(g[k].nivm,g[g[k].l[i]].niv);
}
}
if(ok==1&&k!=1);///punct de articulatie
///cout<<k<<" punct critic"<<'\n';
}
int main()
{
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
g[x].l.push_back(y);
g[y].l.push_back(x);
}
g[1].niv=1;
dfs(1,0);
if(nr>1);///nodul radacina e punct de articulatie
///cout<<1<<" punct critic";
cout<<rez.size()<<'\n';
for(size_t i=0;i<rez.size();i++)
{
sort(rez[i].begin(),rez[i].end());
for(size_t j=0;j<rez[i].size();j++)
cout<<rez[i][j]<<" ";
cout<<'\n';
}
return 0;
}