Cod sursa(job #2144127)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 26 februarie 2018 15:48:54
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <cstring>

using namespace std;

void read(int &n, int &m, vector<int> **G) {
    ifstream f("bfs.in");
    if(!f.is_open()){
        cout<<"The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }
    f>>n>>m;
    (*G) = new vector<int>[n + 1];
    int x, y;
    for(int i = 0; i < m; ++i) {
        f>>x>>y;
        (*G)[x].push_back(y);
        (*G)[y].push_back(x);
    }
    f.close();
}

void DFS(vector<int> *G, int *vis, int x) {
    vis[x] = 1;
    for(vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it) {
        if(vis[*it] == 0) {
            DFS(G, vis, *it);
        }
    }
}

int main() {
    int n, m, answer = 0;
    vector<int> *G = NULL;
    read(n, m, &G);
    int *vis = new int[n + 2];
    fill(vis, vis + n + 1, 0);
    for(int i = 1; i <= n; ++i) {
        if(vis[i] == 0) {
            DFS(G, vis, i);
            ++answer;
        }
    }

    ofstream g("bfs.out");
    if(!g.is_open()) {
        cout<<"The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }
    g<<answer<<'\n';
    g.close();

    //Free up memory
    delete[] vis;
    for(int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    delete[] G;
    return 0;
}