Cod sursa(job #1848279)

Utilizator TincaMateiTinca Matei TincaMatei Data 15 ianuarie 2017 18:34:36
Problema Componente biconexe Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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], low[1+MAX_N], 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;
int ma[MAX_M], mb[MAX_M], top;

int min(int a, int b) {
  if(a < b) return a;
  return b;
}

void dfs(int node, int dep, int papa) {
  int i = last[node];
  depth[node] = low[node] = dep;
  while(i != 0) {
    if(depth[mc[i]] == 0) {
      dfs(mc[i], dep + 1, node);
      low[node] = min(low[node], low[mc[i]]);
      if(dep <= low[mc[i]])
        comp++;
    } else if(mc[i] != papa)
      low[node] = min(low[node], low[mc[i]]);
    i = next[i];
  }
}

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);

  dfs(1, 1, 0);

  FILE *fout = fopen("biconex.out", "w");
  fprintf(fout, "%d\n", comp);
  fclose(fout);
  return 0;
}