Pagini recente » Cod sursa (job #857623) | Cod sursa (job #2882622) | Cod sursa (job #851324) | Cod sursa (job #413336) | Cod sursa (job #625687)
Cod sursa(job #625687)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define N 200001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,nivel[N],nrc,parint[N],st1[N],st2[N],c[N],u;
vector<int> g[N],v[N];
bool vizitat[N],ver[N];
void add(int a,int b) {
int x,y;
++nrc;
do {
x=st1[u];
y=st2[u--];
v[nrc].push_back(y);
} while(x!=a || y!=b);
v[nrc].push_back(x);
}
void c_bi(int nod, int parinte) {
vizitat[nod]=true;
c[nod]=nivel[nod]=nivel[parinte]+1;
parint[nod]=parinte;
vector<int>::iterator it;
int aux;
for(it=g[nod].begin();it!=g[nod].end();++it) if((*it)!=parinte) {
if(!vizitat[*it]) {
st1[++u]=nod;
st2[u]=*it;
c_bi(*it,nod);
if(c[*it]<c[nod])
c[nod]=c[*it];
if(c[*it]>=nivel[nod])
add(nod,*it);
}
else if(*it!=parinte && c[*it]<c[nod])
c[nod]=c[*it];
}
}
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);
out << nrc << "\n";
for(i=1;i<=nrc;++i) {
sort(&v[i][0],&v[i][v[i].size()]);
for(it=v[i].begin();it!=v[i].end();++it)
out << *it << " ";
out << "\n";
}
return 0;
}