Cod sursa(job #2857966)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 26 februarie 2022 18:26:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <vector>
#define MAXN    100000

using namespace std;


vector<int> graph[MAXN];
int marked[MAXN];

void dfs(int id){
  marked[id] = 1;

  int i;
  for(i = 0; i < (int)graph[id].size(); i ++){
    if(marked[ graph[id][i] ] == 0)
      dfs(graph[id][i]);
  }
}

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

  fin = fopen("dfs.in","r");
  fscanf(fin,"%d%d",&n,&m);

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

  nr = 0;
  for(i = 0; i < n; i ++){
    if(marked[i] == 0){
      nr ++;
      dfs(i);
    }
  }

  fout = fopen("dfs.out", "w");
  fprintf(fout, "%d", nr);
  fclose(fout);
  return 0;
}