Cod sursa(job #2926060)

Utilizator briccBriciu Petru Bogdan bricc Data 16 octombrie 2022 19:51:07
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
// Adjascency List representation in C++

#include <fstream>
#include<vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");

  // Create a graph
  vector<int> adj[1001];
int n,m,nr=0;
bool v[1001]={false};

// Add edge
void addEdge(vector<int> adj[], int s, int d) {
  adj[s].push_back(d);
  adj[d].push_back(s);
}

void dfs(int c){
      v[c]=true;
    for (auto x : adj[c]){
      if(!v[x])
      dfs(x);
    }
  }



int main() {
  cin>>n>>m;
  

for(int i=1; i<=m; i++){
  int a,b;
  cin>>a>>b;
  addEdge(adj,a,b);
}
for(int i=1; i<=n; i++){
  if(!v[i]){
    nr++;
  dfs(i);
  }
}
cout<<nr;
}