Cod sursa(job #2237955)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 4 septembrie 2018 00:35:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
#define INF 10000001
using namespace std;

int num_nodes;
int num_edges;
int num_conected_components;
vector<vector <int>> adj(100001);
vector<int> visited(100001);

void dfs(int node) {
    visited[node]=1;
    for(auto next:adj[node])
        if(not visited[next])
            dfs(next);
}

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

    fin>>num_nodes>>num_edges;
    for(int i=1; i<=num_edges; i++) {
        int src,dest;
        fin>>src>>dest;
        adj[src].push_back(dest);
        adj[dest].push_back(src);
    }

    for(int i=1; i<=num_nodes; i++)
        if(not visited[i])
            dfs(i),num_conected_components++;

    fout<<num_conected_components;

    return 0;
}