Pagini recente » Monitorul de evaluare | Cod sursa (job #1681302) | Cod sursa (job #2476151) | Cod sursa (job #1289403) | Cod sursa (job #1610544)
#include <stdio.h>
#define MAXN 100000
#define MAXM 200000
#define INF 2000000000
int ult[MAXN], nod[2 * MAXM], next[2 * MAXM];
int nr, ultm[MAXN], mch[MAXM], nextm[MAXM], drr;
int h[MAXN], hmin[MAXN], sv[MAXM], dsv;
char viz[MAXN], pus[MAXN];
void dfs(int x){
viz[x] = 1;
int poz = ult[x];
while(poz != -1){
if(!viz[nod[poz]]){
h[nod[poz]] = h[x] + 1;
hmin[nod[poz]] = h[nod[poz]];
sv[dsv] = poz / 2;
dsv++;
dfs(nod[poz]);
if(hmin[nod[poz]] >= h[x]){
dsv++;
do{
dsv--;
mch[drr] = sv[dsv - 1];
nextm[drr] = ultm[nr];
ultm[nr] = drr;
drr++;
}while(sv[dsv - 1] != poz / 2);
dsv--;
nr++;
}
else if(hmin[nod[poz]] < hmin[x])
hmin[x] = hmin[nod[poz]];
}
else if(hmin[x] > h[nod[poz]])
hmin[x] = h[nod[poz]];
poz = next[poz];
}
poz = next[poz];
}
int main(){
FILE *in = fopen("biconexe.in", "r");
int n, m, i, x, y, dr = 0, poz, aux;
fscanf(in, "%d%d", &n, &m);
memset(ult, -1, sizeof ult);
for(i = 0; i < m; i++){
fscanf(in, "%d %d", &x, &y);
x--; y--;
nod[dr] = x;
next[dr] = ult[y];
ult[y] = dr;
dr++;
nod[dr] = y;
next[dr] = ult[x];
ult[x] = dr;
dr++;
}
fclose(in);
memset(ultm, -1, sizeof ultm);
h[0] = hmin[0] = 1;
dfs(0);
FILE *out = fopen("biconexe.out", "w");
fprintf(out, "%d\n", nr);
for(i = 0; i < nr; i++){
poz = ultm[i];
while(poz != -1){
if(!pus[nod[2 * mch[poz]]]){
pus[nod[2 * mch[poz]]] = 1;
fprintf(out, "%d ", nod[2 * mch[poz]] + 1);
}
if(!pus[nod[2 * mch[poz] + 1]]){
pus[nod[2 * mch[poz] + 1]] = 1;
fprintf(out, "%d ", nod[2 * mch[poz] + 1] + 1);
}
poz = nextm[poz];
}
poz = ultm[i];
while(poz != -1){
if(pus[nod[2 * mch[poz]]])
pus[nod[2 * mch[poz]]] = 0;
if(pus[nod[2 * mch[poz] + 1]])
pus[nod[2 * mch[poz] + 1]] = 0;
poz = nextm[poz];
}
fputc('\n', out);
}
fclose(out);
return 0;
}