Pagini recente » Cod sursa (job #2700792) | Cod sursa (job #977953) | Cod sursa (job #2811321) | Cod sursa (job #2703035) | Cod sursa (job #1033526)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define DIM 100010
using namespace std;
struct muchie {
int a;
int b;
};
struct nod {
int inf;
nod *adr;
};
nod *V[DIM], *q;
vector<int> L[DIM];
int N, M, X, Y, i, j, comp, s;
muchie r;
int Uz[DIM], Niv[DIM];
muchie S[2*DIM];
int minim (int a, int b) {
return a<b ? a : b;
}
void dfs(int x, int t, int niv, int &nivMin) {
Niv[x] = nivMin = niv;
Uz[x] = 1;
nod *q;
for (q = V[x];q!=NULL;q = q->adr) {
if (q->inf == t)
continue;
if (Uz[q->inf] == 0) {
S[++s].a = x;
S[s].b = q->inf;
int nivMinFiu;
dfs(q->inf, x, niv+1, nivMinFiu);
nivMin = minim(nivMin, nivMinFiu);
if (nivMinFiu >= niv) {
++comp;
do {
r = S[s--];
L[comp].push_back(r.a);
L[comp].push_back(r.b);
} while (!( r.a == x && r.b == q->inf ));
}
} else {
nivMin = minim(nivMin, Niv[q->inf]);
}
}
Niv[x] = nivMin;
}
int main() {
FILE *f = fopen("biconex.in","r");
FILE *g = fopen("biconex.out","w");
fscanf(f,"%d %d",&N, &M);
for (i=1;i<=M;i++) {
fscanf(f,"%d %d",&X, &Y);
q = new nod;
q->inf = Y;
q->adr = V[X];
V[X] = q;
q = new nod;
q->inf = X;
q->adr = V[Y];
V[Y] = q;
}
fclose(f);
int nivMinFiu;
dfs(1, 1, 1, nivMinFiu);
fprintf(g,"%d\n",comp);
for (i=1;i<=comp;i++) {
L[i].push_back(DIM+1);
sort(L[i].begin(), L[i].end());
for (j=0;j<L[i].size()-1;j++)
if (L[i][j] != L[i][j+1])
fprintf(g,"%d ",L[i][j]);
fprintf(g,"\n");
}
return 0;
}