Cod sursa(job #2590138)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 27 martie 2020 16:07:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

vector <vector<int>> neighbours (100001);
bitset <100001> visited;


ifstream fin;
ofstream fout;

int nodes, edges, i, j, n, k, aux, components;

void DFS_search(int where_to_start){
    visited[where_to_start] = true;
    for (vector<int>::iterator it = neighbours[where_to_start].begin(); it!=neighbours[where_to_start].end(); it++)
        if (!visited[*it]) DFS_search(*it);
}



int main (void){
    fin.open("dfs.in");
    fin>>nodes>>edges;
    for (i=1; i<=edges; i++){
        fin>>j>>k;
        neighbours[j].push_back(k);
        neighbours[k].push_back(j);
    }
    fin.close();

    for (i=1; i<=nodes; i++)
        if (!visited[i]) {
            DFS_search(i);
            components++;
        }

    fout.open("dfs.out");
    fout<<components<<"\n";
    fout.close();


    return 0;
}