Pagini recente » Cod sursa (job #466219) | Cod sursa (job #3214122) | your11thnightmare | Cod sursa (job #610257) | Cod sursa (job #625408)
Cod sursa(job #625408)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define N 100001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,nivel[N],nrc,parint[N];
vector<int> g[N],v[N];
bool vizitat[N],ver[N];
void scrie(int nod, int parinte) {
v[++nrc].push_back(nod);
while(nod!=parinte) {
nod=parint[nod];
v[nrc].push_back(nod);
}
}
void c_bi(int nod, int parinte, int niv, int &niv_min) {
if(vizitat[nod])
niv_min=nivel[nod];
else {
vizitat[nod]=true;
nivel[nod]=niv_min=niv;
parint[nod]=parinte;
vector<int>::iterator it;
int aux;
for(it=g[nod].begin();it!=g[nod].end();++it) if((*it)!=parinte) {
c_bi(*it,nod,niv+1,aux);
if(niv<=aux)
scrie(*it,nod);
if(aux<niv_min)
niv_min=aux;
}
}
}
int main() {
int i,a,b,aux,j,vver;
vector<int>::iterator it;
in >> n >> m;
for(i=1;i<=m;++i) {
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
c_bi(1,0,1,aux);
for(i=1;i<=nrc;++i)
sort(&v[i][0],&v[i][v[i].size()]);
for(i=1;i<nrc;++i) if(v[i].size()<v[i+1].size()) {
vver=0;
for(j=0;j!=v[i].size();++j)
if(v[i][j]!=v[i+1][j])
vver=1;
if(vver==0) {
--nrc;
ver[i]=true;
}
}
out << nrc << "\n";
for(i=1;i<=nrc;++i) {
if(ver[i]) {
++nrc;
continue;
}
for(it=v[i].begin();it!=v[i].end();++it)
out << *it << " ";
out << "\n";
}
return 0;
}