Cod sursa(job #2668687)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 5 noiembrie 2020 09:55:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

const int max_up = 1e5 + 5;

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

vector <int> g[max_up];
vector <bool> verified(max_up, false);

void dfs (int u)
{
    verified[u] = true;
    for(auto v : g[u])
        if(!verified[v])
            dfs(v);
}

int main()
{
    int n, m; fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v; fin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        if(!verified[i]){
            dfs(i);
            ans++;
        }
    }
    fout << ans;
    return 0;
}