Cod sursa(job #1848125)

Utilizator TincaMateiTinca Matei TincaMatei Data 15 ianuarie 2017 15:20:30
Problema Componente biconexe Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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];
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;

void dfs(int node, int d, int papa) {
  int i = last[node];
  low[node] = d;
  viz[node] = true;
  while(i != 0) {
    if(mc[i] != papa) {
      if(!viz[mc[i]]) {
        dfs(mc[i], d + 1, node);
        if(low[mc[i]] < low[node])
          low[node] = low[mc[i]];
        if(d <= low[mc[i]]) {
          comp++;
        }
      } else if(low[mc[i]] < low[node])
        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);

  for(int i = 1; i <= n; ++i)
    if(!viz[i])
      dfs(i, 0, 0);

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