Cod sursa(job #3228021)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 4 mai 2024 19:55:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
#define MAXN 1000001

using namespace std;

vector<int> graph[MAXN];

bool mark[MAXN];

int n, m;

void dfs(int parent){
  mark[parent] = true;
  for(int i=0; i<graph[parent].size(); i++){
    if(!mark[graph[parent][i]]) dfs(graph[parent][i]);
  }
}

int main(){
  FILE *fin, *fout;
  fin = fopen("dfs.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i=0; i<m; i++){
    int a; int b;
    fscanf(fin, "%d%d", &a, &b);
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  fclose(fin);

  int total = 0;
  for(int i=1; i<=n; i++){
    if(!mark[i]){
      dfs(i); total++;
    }
  }

  fout = fopen("dfs.out", "w");
  fprintf(fout, "%d\n", total);
  fclose(fout);
}