Cod sursa(job #1610544)

Utilizator hrazvanHarsan Razvan hrazvan Data 23 februarie 2016 17:13:09
Problema Componente biconexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.12 kb
#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;
}