Pagini recente » Cod sursa (job #2682572) | Cod sursa (job #2466240) | Cod sursa (job #1657797) | Cod sursa (job #2672300) | Cod sursa (job #2323575)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nma[100003],nivel[100003],nrcomp;
bool viz[100003];
set<pair<int, int> >punti;
set<int>critice;
vector<int>v[100003];
stack<int>s;
vector<int>comp[100003];
void dfs(int k, int tata)
{
s.push(k);
int x;
vector<int>::iterator it;
viz[k]=1;
nivel[k]=nivel[tata]+1;
nma[k]=nivel[k];
for(it=v[k].begin();it!=v[k].end();++it)
{
x=*it;
if(x!=tata)
{
if(viz[x]){
if(nma[k]>nivel[x]) nma[k]=nivel[x];
}
else{
dfs(x,k);
if(nma[k]>nma[x]) nma[k]=nma[x];/*
///pcte de articulatie
if(nivel[k]<=nma[x] && k!=1) critice.insert(k);
///punti
if(nivel[k]<nma[x]) punti.insert(make_pair(k,x));*/
///comp 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()
{
int i,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
///=================/
/*
set<int>::iterator it;
for(it=critice.begin();it!=critice.end();++it) g<<*it<<' ';
g<<'\n';
///=================
set<pair<int, int> >::iterator it1;
for(it1=punti.begin();it1!=punti.end();++it1) g<<it1->first<<' '<<it1->second<<'\n';*/
///=================
g<<nrcomp<<'\n';
vector<int>::iterator it2;
for(i=1;i<=nrcomp;i++)
{
for(it2=comp[i].begin();it2!=comp[i].end();++it2) g<<*it2<<' ';
g<<'\n';
}
f.close();
g.close();
return 0;
}