Cod sursa(job #2792288)

Utilizator izotova_dIzotova Daria izotova_d Data 1 noiembrie 2021 13:04:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<bool> visited;

class Graph
{
private:
	//number of nodes
	int n;
	//number of edges
	int e;
	//adj list for graph representation
	vector<vector<int>> adj_list;
public:
	Graph(int n)
	{
		this->n = n;
		this->e = 0;
		vector<int> empty;
		for (unsigned int i = 0; i < n; i++)
		{
			this->adj_list.push_back(empty);
		}
	}
	virtual ~Graph() {}

	void add_edge(int node1, int node2)
	{
		this->e++;
		this->adj_list[node1].push_back(node2);
		this->adj_list[node2].push_back(node1);
	}
	

	void dfs(int start_node)
	{
		visited[start_node] = true;

		for (unsigned int i = 0; i < adj_list[start_node].size(); i++)
		{
			int current_node;
			current_node = adj_list[start_node][i];
			if (visited[current_node] == false)
			{
				dfs(current_node);
			}
		}

	}
};



int main()
{
	int cnt = 0;
	//number of nodes
	int N;
	//number of edges
	int E;
	fin >> N >> E;
	Graph graph(N);
	int n1, n2;
	for (unsigned int i = 0; i < E; i++)
	{
		fin >> n1 >> n2;
		graph.add_edge(n1 - 1, n2 - 1);
	}

	for (unsigned int i = 0; i < N; i++)
	{
		visited.push_back(false);
	}
	
	for (unsigned int i = 0; i < N; i++)
	{
		if (!visited[i])
		{
			cnt++;
			graph.dfs(i);
		}
	}
	fout << cnt;
	return 0;
}