Pagini recente » Cod sursa (job #799119) | Cod sursa (job #1383023) | Cod sursa (job #305251) | Cod sursa (job #305105) | Cod sursa (job #633450)
Cod sursa(job #633450)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int N,M;
typedef pair<int,int> PII;
stack<PII> S;
vector<int> nr[100100];
vector<vector<int> > CB;
int tata[100100],low[100100],dfn[100100];
inline int min(int a,int b){
return a<b?a:b;
}
void CBC(int x,int y){
vector<int> aux;
int sx,sy;
do{
sx=S.top().first;
sy=S.top().second;
S.pop();
aux.push_back(sx);
aux.push_back(sy);
}while(sx!=x || sy!=y);
sort(aux.begin(),aux.end());
aux.erase(unique(aux.begin(),aux.end()),aux.end());
CB.push_back(aux);
}
void df(int x,int ad){
dfn[x]=low[x]=ad;
for(vector<int>::iterator it=nr[x].begin();it!=nr[x].end();++it){
if(*it==tata[x])
continue;
if(dfn[*it]==-1){
tata[*it]=x;
S.push(PII(x,*it));
df(*it,ad+1);
low[x]=min(low[x],low[*it]);
if(low[*it]>=dfn[x])
CBC(x,*it);
}
else
low[x]=min(low[x],dfn[*it]);
}
}
int main(){
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int i,x,y;
scanf("%d%d",&N,&M);
for(i=0;i<M;++i){
scanf("%d%d",&x,&y);
nr[x].push_back(y);
nr[y].push_back(x);
}
for(i=1;i<=N;++i)
dfn[i]=-1;
df(1,0);
printf("%d\n",CB.size());
for(i=0;i<(int)CB.size();++i){
for(vector<int>::iterator it=CB[i].begin();it!=CB[i].end();++it)
printf("%d ",*it);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}