Pagini recente » Rating Fur Fur (furfur233) | Cod sursa (job #2665901) | Cod sursa (job #532109) | Cod sursa (job #1695810) | Cod sursa (job #634457)
Cod sursa(job #634457)
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;
#define nmax 100010
int n, m, k, vf=-1;
int nivel[nmax], nma[nmax];//nivelul minim de acces
bitset <nmax>viz;
struct nod{
int a,b;
}stiva[nmax];
vector <int> lista[nmax], S[nmax];
void dfs(int nc) {
viz[nc] = 1;
nma[nc] = nivel[nc];
for (vector <int>::iterator it = lista[nc].begin(); it != lista[nc].end(); ++it)//iau la rand toti vecinii lui nc/nod curent
if (viz[*it] == 0){
nivel[*it] = nivel[nc] + 1;
vf++;
stiva[vf].a = nc;
stiva[vf].b = *it;
dfs(*it);
if (nma[*it] >= nivel[nc]) { //am gasit o componenta biconexa
while (!(stiva[vf].a == nc && stiva[vf].b == *it)) {
S[k].push_back(stiva[vf].b);
vf--;
}
S[k].push_back(nc);
S[k].push_back(*it);
vf--;
k++;
}
nma[nc] = min(nma[nc], nma[*it]);
}
else
nma[nc] = min(nma[nc], nivel[*it]);
}
int main() {
int i;
FILE *fin=fopen("biconex.in", "r");
FILE *fout=fopen("biconex.out", "w");
fscanf(fin,"%d %d", &n, &m);
int a,b;
for (i =0; i<m; i++) {
fscanf(fin,"%d %d", &a, &b);
lista[a].push_back(b);
lista[b].push_back(a);
}
dfs(1);
fprintf(fout,"%d\n", k);
for(i = 0; i <k; i++) {
for (vector <int>::iterator it = S[i].begin(); it != S[i].end(); ++it)
fprintf(fout,"%d ", *it);
fprintf(fout,"\n");
}
return 0;
}