Cod sursa(job #2969123)

Utilizator popica312Pop David-Gabriel popica312 Data 22 ianuarie 2023 16:34:36
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector> 

using namespace std;

ifstream cin("DFS.in");
ofstream cout("DFS.out");



vector <int> G[100005];

int n, m, x, y, cnt;
bool visited[100005];

void DFS(int node){
     visited[node] = true;
     for (int i = 0; i < G[node].size(); ++i){
          if (!visited[G[node][i]]){
               DFS(G[node][i]);
          }
     }
}

int main()
{
     cin >> n >> m;
     
     // citire
     for (int i = 0; i < m; ++i)
     {
          cin >> x >> y;
          G[x].push_back(y);
          G[y].push_back(x);
     }
     
     
     //cautare si afisare comp_Conexe
     for(int i = 1; i <= n; ++i){
          if (visited[i] == 0)
          {
               ++cnt;
               DFS(i);
          }
     }
     cout << cnt;
     return 0;
}