Pagini recente » Cod sursa (job #1984628) | Cod sursa (job #2414960) | Cod sursa (job #1563259) | Cod sursa (job #2600168) | Cod sursa (job #1563749)
#include<cstdio>
#include<vector>
#include<set>
#define N 100000
#define M 200000
using namespace std;
bool viz[N+1];
int lst[N+1];
int urm[2*M+1];
int vecin[2*M+1];
vector<set<int> > comp;
set<int> aux;
int xstk[M+1];
int ystk[M+1];
int k;
int nivel[N+1];
int dfs(int nod){
int p,up,x;
viz[nod]=true;
up=nivel[nod];
p=lst[nod];
while(p!=0){
if (viz[vecin[p]]==false){
nivel[vecin[p]]=nivel[nod]+1;
k++;
xstk[k]=nod;
ystk[k]=vecin[p];
x=dfs(vecin[p]);
if (x>=nivel[nod]){
comp.push_back(aux);
comp[comp.size()-1].insert(xstk[k]);
comp[comp.size()-1].insert(ystk[k]);
while(k>1 &&(xstk[k]!=nod ||ystk[k]!=vecin[p])){
k--;
comp[comp.size()-1].insert(xstk[k]);
comp[comp.size()-1].insert(ystk[k]);
}
k--;
}
else
if (up>x) up=x;
}
else
if (nivel[vecin[p]]<up) up=nivel[vecin[p]];
p=urm[p];
}
return up;
}
void adauga(int x,int y,int i){
vecin[i*2-1]=y;
urm[i*2-1]=lst[x];
lst[x]=i*2-1;
vecin[i*2]=x;
urm[i*2]=lst[y];
lst[y]=i*2;
}
int main(){
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
int n,m,i,x,y;
scanf ("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf ("%d%d",&x,&y);
adauga(x,y,i);
}
dfs(1);
printf ("%d\n",comp.size());
set<int>::iterator it;
for(i=0;i<comp.size();i++){
for(it=comp[i].begin();it!=comp[i].end();it++)
printf ("%d ",*it);
printf ("\n");
}
return 0;
}