Cod sursa(job #1847965)

Utilizator TincaMateiTinca Matei TincaMatei Data 15 ianuarie 2017 12:02:13
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>

const int MAX_N = 100000;
const int MAX_M = 200000;

int last[1+MAX_N], mc[1+2*MAX_M], next[1+2*MAX_M], depth[1+MAX_N];
bool viz[1+MAX_N];

inline void addM(int a, int b, int id) {
  next[id] = last[a];
  mc[id] = b;
  last[a] = id;
}

int comp, nod[2*MAX_N], bic[2*MAX_N], topBic;

void dfs(int node, int d, int &low) {
  int i = last[node];
  depth[node] = d;
  viz[node] = true;
  while(i != 0) {
    if(viz[mc[i]] && depth[mc[i]] < low)
      low = depth[mc[i]];
    else if(!viz[mc[i]]) {
      int up = 1000000000;
      dfs(mc[i], d + 1, up);
      if(up < low)
        low = up;
      if(d <= up) {//punct de articulatie
        nod[topBic] = node;
        bic[topBic++] = comp;
        comp++;
      }
    }
    i = next[i];
  }
  if(d > 1) {
    nod[topBic] = node;
    bic[topBic++] = comp;
  }
}

int main() {
  int n, m, a, b;
  FILE *fin = fopen("biconex.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    fscanf(fin, "%d%d", &a, &b);
    addM(a, b, i * 2 - 1);
    addM(b, a, i * 2);
  }
  fclose(fin);

  for(int i = 1; i <= n; ++i)
    if(!viz[i]) {
      int up = 1000000000;
      dfs(i, 1, up);
    }

  FILE *fout = fopen("biconex.out", "w");
  fprintf(fout, "%d\n", comp);
  int last = bic[0];
  for(int i = 0; i < topBic; ++i) {
    if(bic[i] == last)
      fprintf(fout, "%d ", nod[i]);
    else {
      fprintf(fout, "\n%d ", nod[i]);
      last = bic[i];
    }
  }
  fclose(fout);
  return 0;
}