Pagini recente » Cod sursa (job #810776) | Cod sursa (job #809420) | Cod sursa (job #556610) | Cod sursa (job #568903) | Cod sursa (job #521901)
Cod sursa(job #521901)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define file_in "biconex.in"
#define file_out "biconex.out"
#define nmax 200102
int niv[nmax];
int viz[nmax];
int v[nmax];
vector<int> G[nmax];
int stiva1[nmax];
int stiva2[nmax];
int nr;
vector<int> sol[nmax];
int n,m,u;
void baga(int a, int b){
int x,y;
nr++;
do{
x=stiva1[u];
y=stiva2[u--];
sol[nr].push_back(y);
}
while(x!=a || y!=b);
sol[nr].push_back(x);
}
void dfs(int nod, int tata){
niv[nod]=niv[tata]+1;
viz[nod]=1;
v[nod]=niv[nod];
vector<int> :: iterator it;
for (it=G[nod].begin();it!=G[nod].end();++it){
if (!viz[*it]){
stiva1[++u]=nod;
stiva2[u]=*it;
dfs(*it,nod);
if (v[*it]<v[nod]) v[nod]=v[*it];
if (v[*it]>=niv[nod]) baga(nod,*it);
}
else{
if (*it!=tata && v[*it]<v[nod]) v[nod]=v[*it];
}
}
}
int main(){
int i,a,b,j;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;++i){
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1,0);
printf("%d\n",nr);
for(i=1;i<=nr;++i)
{
sort(sol[i].begin(),sol[i].end());
for(j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}