Cod sursa(job #2424770)

Utilizator SternulStern Cristian Sternul Data 23 mai 2019 20:35:23
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
//
// Created by Cristian Stern on 5/23/2019.
//

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void DFS(int nod, int cmp, vector < vector < int > > G, vector < int > &viz){
    viz[nod] = cmp;
    for(auto vecin:G[nod]){
        if(viz[vecin] == 0)
            DFS(vecin, cmp, G, viz);
    }
}

int main(){
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    //ifstream f("E:\\FMI\\AG\\lab3\\date.in");
    //ofstream g("E:\\FMI\\AG\\lab3\\date.out");
    unsigned  long long int n;
    int m, x, y;
    f >> n >> m;

    vector < vector < int > > G(5 + n);
    vector < int > viz(5 + n, 0);
    for(int i = 0;i < m;i++){
        f>>x>>y;
        x--;
        y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int comp = 0;
    int nr_viz = 1;
    for(int i = 0; i < n;i++){
        if(viz[i] == 0){
            comp++;
            DFS(i, nr_viz, G, viz);
        }
        nr_viz++;
    }
    g<<comp;
}