Cod sursa(job #2693152)

Utilizator Gota_AndreiGota Andrei Gota_Andrei Data 4 ianuarie 2021 23:08:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n,m,i,x,y,contor;
vector< int > muchii[100005];
bool vizitat [100005];

void DFS (int NOD){
  vizitat[NOD]=true;

  for (unsigned int i=0;i<muchii[NOD].size();i++){
    int vecin=muchii[NOD][i];
    if (!vizitat[vecin])
       DFS(vecin);
  }
}

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

  for (i=1;i<=m;i++){
    fin>>x>>y;
    muchii[x].push_back(y);
    muchii[y].push_back(x);
  }

  for (i=1;i<=n;i++){
    if (!vizitat[i]){
      contor++;
      DFS(i);
    }
  }

  fout<<contor<<"\n";
}