Cod sursa(job #1848076)

Utilizator TincaMateiTinca Matei TincaMatei Data 15 ianuarie 2017 14:26:46
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 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], 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 i = last[node];
  depth[node] = d;
  low[node] = d;
  viz[node] = true;
  while(i != 0) {
    if(!viz[mc[i]]) {
      ma[top] = node;
      mb[top] = mc[i];
      ++top;
      dfs(mc[i], d + 1);
      if(low[mc[i]] < low[node])
        low[node] = low[mc[i]];
      if(d <= low[mc[i]]) {
        nod[topBic] = node;
        bic[topBic] = comp;
        topBic++;
        do {
          nod[topBic] = mb[top - 1];
          bic[topBic] = comp;
          topBic++;
          --top;
        } while(top > 0 && (ma[top] != node || mb[top] != 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, 1);

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