Cod sursa(job #3229333)

Utilizator cret007Andrei Cret cret007 Data 15 mai 2024 11:22:29
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

#define MAX_NODE 100001
#define cin fin 
#define cout fout 

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

vector <vector <int>> adj(MAX_NODE);
vector <bool> visited(MAX_NODE, false);
int edges, nodes;
int components = 0;


void dfs (int node) {
    
    visited[node] = true;
    //printf("%d ", node);

    for (auto j: adj[node]) {
        if (!visited[j])
            dfs(j);
    }
}


int main() {

    cin>>nodes>>edges;
    int x, y;

    for (int i = 0; i < edges; i++) {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= nodes; i++) {
        if (!visited[i]) {
            components++;
            dfs(i);
        }
    }

    printf("%d", components);

    fin.close();
    fout.close();
    
    return 0;
}