Cod sursa(job #2432466)

Utilizator ShayTeodor Matei Shay Data 23 iunie 2019 19:57:10
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <vector>

void dfs(int src, std::vector<bool> &visited, std::vector<int> *adj) {
	visited[src] = true;
	for (int i = 0 ; i < adj[src].size() ; ++i) {
		if (!visited[adj[src][i]]) {
			visited[adj[src][i]] = true;
			dfs(adj[src][i], visited, adj);
		}
	}
}

int get_nr_components(int src, std::vector<bool> &visited, std::vector<int> *adj, int &N) {
	int counter = 0;

	for (int i = 1 ; i <= N ; ++i) {
		if (!visited[i]) {
			++counter;
			visited[i] = true;
			dfs(i, visited, adj);
		}
	}

	return counter;
}

int main() {
	int N, M, src, dest;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d%d", &N, &M);
	assert(1 <= N && N <= 100000);
	assert(0 <= M && M <= std::min(N * (N + 1) / 2, 200000));

	std::vector<int> *adj = new std::vector<int>[N + 1];
	std::vector<bool> visited(N, false);

	for (; M; --M) {
		scanf("%d %d", &src, &dest);
		adj[src].push_back(dest);
		adj[dest].push_back(src);
	}
		
	int counter = get_nr_components(src, visited, adj, N);

	printf("%d\n", counter);
	delete [] adj;
	return 0;
}