Cod sursa(job #2816562)

Utilizator walentines44Serban Valentin walentines44 Data 11 decembrie 2021 16:04:25
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

void explore(vector<vector<int>> adj_list, int x, vector<bool> &visited){
    visited[x] = true;
    vector<int>::iterator i;
    for(i = adj_list[x].begin(); i < adj_list[x].end(); ++i){
        if(!visited[*i]){
	        explore(adj_list, *i, visited);
	    }
    }
}

int nr_conexe(vector<vector<int>> adj_list){
    vector<bool> visited(adj_list.size(), false);
    int cnt = 0;
    for(unsigned i = 0; i < adj_list.size(); ++i){
        if(!visited[i]){
	    cnt++;
	    explore(adj_list, i, visited);
	}
    }

    return cnt;
}

int main(){
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    unsigned int N, M;
    int x, y;
    fin >> N >> M;
    //cout << N << " " << M;
    //cout << "\n";
    vector<vector<int>> adj_list(N, vector<int>());
    for(unsigned int i = 0; i < M; ++i){
    	fin >> x >> y;
	    adj_list[x - 1].push_back(y - 1);
	    adj_list[y - 1].push_back(x - 1);	
    }
    //for(int i = 0; i < N; ++i){
        //for(unsigned j = 0; j < adj_list[i].size(); ++j){
	    //cout << i + 1 << " " << adj_list[i][j] + 1 << " ";
	    //cout << "\n";
	//}
    //}
    int nr = nr_conexe(adj_list);
    fout << nr;

    return 0;
}