Cod sursa(job #1997583)

Utilizator vtemianVlad Temian vtemian Data 4 iulie 2017 21:37:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

map<int, vector<int> > graf;

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

int visited[100005];

void dfs(int current_node) {
    visited[current_node] = 1;

    for (auto &node : graf[current_node]) {
        if (!visited[node]) {
            dfs(node);
        }
    }
}

int main() {
    int count=0, n, m, start, end, components=0;

    fin >> n >> m;

    count = 1;
    while (count <= n) {
        vector<int> vecini;
        graf[count] = vecini;
        ++count;
    }

    count = 0;
    while (count < m) {
        fin >> start >> end;

        graf[start].push_back(end);
        graf[end].push_back(start);

        ++count;
    }

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

    fout << components;
    return 0;
}