Cod sursa(job #2930247)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 27 octombrie 2022 20:16:53
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdio.h>
#include <vector>

#define MAXN 100005

struct nod {
  bool viz = false;
  int depth = 0;
  std::vector<int> chd;
};

struct stk_elem {
  int nod;
  int anc;
};

nod web[MAXN];

std::vector<stk_elem> stk;

std::vector<std::vector<int>> comps;

int DFS(int nod, int depth) {
  //printf("%d Depth: %d\n", nod, depth);
  web[nod].depth = depth;
  stk.push_back({nod, depth});
  for (int i = 0; i < web[nod].chd.size(); i++) {
    if (web[web[nod].chd[i]].depth) {
      stk.back().anc = std::min(stk.back().anc, web[web[nod].chd[i]].depth);
      //printf("%d Upper Edge %d\n", nod, web[web[nod].chd[i]].depth);
    }
		else if (!web[web[nod].chd[i]].viz) {
			int val = DFS(web[nod].chd[i], depth + 1);
      stk.back().anc = std::min(stk.back().anc, val);
      //printf("%d New Edge %d\n", nod, val);
    }
  }
  int ret = stk.back().anc;
  stk.pop_back();
  if (!stk.empty()) {
    if (stk.size() == ret) {
      comps.back().push_back(nod);
      comps.back().push_back(stk.back().nod);
      comps.emplace_back();
      //printf("%d New component %d\n", nod, ret);
    }
		else {
      comps.back().push_back(nod);
      //printf("%d Added %d %d\n", nod, (int)stk.size(), ret);
    }
  }
  web[nod].depth = 0;
  web[nod].viz = true;
  return ret;
}

int main() {
  FILE *fin, *fout;
  int n, m;
  int a, b;
  int i;

  fin = fopen("biconex.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;
    web[a].chd.push_back(b);
    web[b].chd.push_back(a);
  }

  fclose(fin);

  for (int i = 0; i < n; i++) {
    if (!web[i].viz) {
      comps.emplace_back();
      DFS(i, 1);
    }
  }

  fout = fopen("biconex.out", "w");

  fprintf(fout, "%d\n", (int)comps.size());
  for (int i = 0; i < comps.size(); i++) {
    for (int j = 0; j < comps[i].size(); j++) {
      fprintf(fout, "%d ", comps[i][j] + 1);
    }
    fprintf(fout, "\n");
  }

  fclose(fout);
}