Cod sursa(job #2814978)

Utilizator walentines44Serban Valentin walentines44 Data 8 decembrie 2021 21:48:19
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.19 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;
    for(unsigned int i = 0; i < adj_list[x].size(); ++i){
        if(!visited[adj_list[x][i]]){
	    explore(adj_list, adj_list[x][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;
}