Cod sursa(job #2633872)

Utilizator KlinashkaDiacicov Calin Marian Klinashka Data 8 iulie 2020 23:52:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.53 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

const int NMAX=1e5;

int N;
vector<int> adj[NMAX+1];
bool visit[NMAX+1];

void citire() {
	int M, a, b;
	cin>>N>>M;
	for(int i=1;i<=M;++i) {
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
}

void dfs(int v) {
	visit[v]=true;
	for(auto e:adj[v]) {
		if(!visit[e]) {
			dfs(e);
		}
	}
}

int main() {
	int k=0;
	citire();
	for(int i=1;i<=N;++i) {
		if(!visit[i]) {
			++k;
			dfs(i);
		}
	}
	cout<<k<<'\n';
	return 0;
}