Cod sursa(job #2935383)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 6 noiembrie 2022 17:11:28
Problema Ciclu hamiltonian de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <vector>

#define MAXN 100005

struct nod {
  bool done = false;
  int depth = -1;
  int anc;
  std::vector<int> chd;
};

nod web[MAXN];

std::vector<int> stk;

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

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

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].done) {
      DFS(i, 1, -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);
}