Cod sursa(job #2924067)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 24 septembrie 2022 11:58:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

#define MAX_N 100005

struct Node {
  vector<int> edges;
};
Node nodes[MAX_N];

int marked[MAX_N];

void myFill(int node) {
  marked[node] = 1;
  for (int ngh : nodes[node].edges)
    if (marked[ngh] == 0)
      myFill(ngh);
}

int main() {
  FILE *fin, *fout;
  int n, m;
  int node1, node2;
  int index;
  int res;

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

  fscanf(fin, "%d%d", &n, &m);
  for (index = 0; index < m; index++) {
    fscanf(fin, "%d%d", &node1, &node2);
    nodes[node1].edges.push_back(node2);
    nodes[node2].edges.push_back(node1);
  }

  fclose(fin);

  res = 0;
  for (index = 1; index <= n; index++) {
    if (marked[index] == 0) {
      myFill(index);
      res++;
    }
  }

  fout = fopen("dfs.out", "w");
  fprintf(fout, "%d", res);
  fclose(fout);

  return 0;
}