Cod sursa(job #1992931)

Utilizator palarie1Serban Vlad Stefan palarie1 Data 21 iunie 2017 21:46:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector<bool> vis;
vector<vector<int> > graph;


void DFS(int x) {
    vis.at(x) = true;
    for (int i = 0 ; i < graph.at(x).size() ; i++) {
        int y = graph.at(x).at(i);
        if (!vis.at(y)) {
            DFS(y);
        }
    }
}

int main() {

    ifstream in("dfs.in");

    int n, m;
    in >> n >> m;
    graph.resize(n);

    for (int i = 0 ; i < m ; i++) {
        int x, y;
        in >> x >> y;
        x = x - 1;
        y = y - 1;
        graph.at(x).push_back(y);
        graph.at(y).push_back(x);
    }
    vis.resize(n, false);

    int k = 0;

    for (int i = 0 ; i < vis.size() ; i++){
        if (!vis.at(i)) {
            DFS(i);
            k++;
        }
    }

    ofstream out("dfs.out");
    out << k << "\n";
    return 0;
}