Cod sursa(job #2666323)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 1 noiembrie 2020 15:22:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>

using namespace std;

int n, m, i, j, k;
vector<int> v[100005];
vector<bool> viz(100005, false);

void dfs(int nod) {
    int p;

    if(!viz[nod]) {
        viz[nod] = true;
        for(p = 0; p < v[nod].size(); p++)
            if(!viz[v[nod][p]])
                dfs(v[nod][p]);
    }
}

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f >> n >> m;
    while(m) {
        f >> i >> j;

        v[i].push_back(j);
        v[j].push_back(i);
        m--;
    }
    f.close();

    k = 0;
    for(i = 1; i <= n; i++)
        if(!viz[i]) {
            k++;
            dfs(i);
        }

    g << k << '\n';
    g.close();

    return 0;
}