Cod sursa(job #2799023)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 12 noiembrie 2021 10:40:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 100000

vector <int>arb[MAXN];
int marcat[MAXN];

void ffill(int nod){
  int i;
  marcat[nod] = 1;
  for(i = 0; i < arb[nod].size(); i++){
    if(marcat[arb[nod][i]] == 0){
      ffill(arb[nod][i]);
    }
  }
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, a, b, nrcc;
    fin = fopen("dfs.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 0; i < m; i++){
      fscanf(fin, "%d%d", &a, &b);
      arb[a - 1].push_back(b - 1);
      arb[b - 1].push_back(a - 1);
    }
    fclose(fin);
    nrcc = 0;
    for(i = 0; i < n; i++){
      if(marcat[i] == 0){
        ffill(i);
        nrcc++;
      }
    }
    fout = fopen("dfs.out", "w");
    fprintf(fout, "%d", nrcc);
    fclose(fout);
    return 0;
}