Pagini recente » Cod sursa (job #2290550) | Cod sursa (job #697390) | Cod sursa (job #1312774) | Profil fotadavid23 | Cod sursa (job #1607994)
#include <cstdio>
#include <vector>
#define MAXN 100000
#define MAXM 200000
std::vector <int> v[MAXN];
int vf, t, k, val[2*MAXM+1], next[2*MAXM+1], lista[MAXN+1], viz[MAXN+1], h[MAXN+1], hmin[MAXN+1], st[MAXM+1];
inline void add(int x, int y){
if(v[x].size()==0){
v[x].push_back(val[2*y+1]);
v[x].push_back(val[2*y+2]);
}else{
if(val[2*y+1]==v[x][v[x].size()-1]){
v[x].push_back(val[2*y+2]);
}else{
v[x].push_back(val[2*y+1]);
}
}
}
inline void adauga(int x, int y){
t++;
val[t]=y;
next[t]=lista[x];
lista[x]=t;
}
void dfs(int x){
int p=lista[x];
viz[x]=1;
hmin[x]=h[x];
while(p){
if(viz[val[p]]==0){
h[val[p]]=h[x]+1;
st[++vf]=(p-1)/2;
dfs(val[p]);
if(hmin[val[p]]<h[x]){
if(hmin[x]>hmin[val[p]]){
hmin[x]=hmin[val[p]];
}
}else{
while(st[vf]!=(p-1)/2){
add(k, st[vf]);
vf--;
}
add(k, st[vf]);
vf--;
k++;
}
}else{
if(hmin[x]>h[val[p]]){
hmin[x]=h[val[p]];
}
}
p=next[p];
}
}
int main(){
int n, m, x, y, i, j;
FILE *fin, *fout;
fin=fopen("biconex.in", "r");
fout=fopen("biconex.out", "w");
fscanf(fin, "%d%d", &n, &m);
for(i=0; i<m; i++){
fscanf(fin, "%d%d", &x, &y);
adauga(x, y);
adauga(y, x);
}
dfs(1);
fprintf(fout, "%d\n", k);
for(i=0; i<k; i++){
for(j=0; j<(int)v[i].size(); j++){
fprintf(fout, "%d ", v[i][j]);
}
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}