Cod sursa(job #2981381)

Utilizator 222cezarCezar Stilpeanu 222cezar Data 17 februarie 2023 20:44:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e5;
vector<vector<int>> adj(N);
bool visited[N];

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

int main() {
   int n, m;
   in >> n >> m;
   for(int i = 0; i < m; i++) {
       int x, y;
       in >> x >> y;
       x--, y--;
       adj[x].push_back(y);
       adj[y].push_back(x);
   }
   int cnt = 0;
   for(int i = 0; i < n; i++) {
       if(!visited[i])  { dfs(i); cnt++; }
   }
   out << cnt << '\n';
}