Cod sursa(job #3229019)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 12 mai 2024 23:10:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int nmax = 1e5+10;
int n,m;
vector<vector<int>> mat(nmax);
vector<int> visited(nmax);
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2;
		mat[nod_1].push_back(nod_2);
		mat[nod_2].push_back(nod_1);
	}
};
void dfs(int nod){
	visited[nod] = 1;
	for(auto nod_aux : mat[nod]){
		if(!visited[nod_aux]){
			dfs(nod_aux);
		}
	}
};
void solve(){
	int numar = 0;
	for(int i = 1; i <=n; i++){
		if(!visited[i]){
	      numar++;
	      dfs(i);
	      }
	};
	fout << numar;
}
int main(){
	read_input();
	solve();
	return 0;
}