Cod sursa(job #2424760)

Utilizator SternulStern Cristian Sternul Data 23 mai 2019 20:28:27
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 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;
    try {
        f >> n >> m;
        if (n <= 0)
            throw 5;
    }
    catch (int x){
        x = -x;
    }

    vector < vector < int > > G(n);
    vector < int > viz(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 = 0;
    for(int i = 0; i < n;i++){
        if(viz[i] == 0){
            comp++;
            DFS(i, comp, G, viz);
        }
    }
    g<<comp;
}