Cod sursa(job #2855140)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 22 februarie 2022 09:55:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

#define MAX_N 100005

vector<int> graph[MAX_N];

bool conex[MAX_N];

void addEdge(int a, int b) {
  graph[a].push_back(b);
  graph[b].push_back(a);
}

void dfs(int node) {
  conex[node] = 1;

  for(int neighbour : graph[node]){
    if(!conex[neighbour]){
      dfs(neighbour);
    }
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("dfs.in", "r");
  fout = fopen("dfs.out", "w");

  int n, m, i, a, b, c;
  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; ++i) {
    fscanf(fin, "%d%d", &a, &b);
    addEdge(a, b);
  }

  c=0;
  for (i = 1; i <= n; ++i){
    if(conex[i] == 0){
      dfs(i);
      c++;
    }
  }

  fprintf(fout, "%d", c);

  fclose(fin);
  fclose(fout);
  return 0;
}