Cod sursa(job #2307615)

Utilizator AngelEclipseGarleanu Alexandru Stefan AngelEclipse Data 25 decembrie 2018 02:16:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>

std::stack <int> s;
int n, m, conexe = 0;
std::vector <int> graf[100005];
bool viz[100005];

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

void dfs(int nod) {
    viz[nod] = true;
    for(int i = 0; i < graf[nod].size(); i++)
        if(!viz[graf[nod][i]])
            dfs(graf[nod][i]);
}

int main() {
    in>>n>>m;
    for(int i = 1; i <= m; ++i) {
        int node1, node2;
        in>>node1>>node2;
        graf[node1].push_back(node2);
        graf[node2].push_back(node1);
    }

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

    out<<conexe;

    return 0;
}