Cod sursa(job #2784536)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 16 octombrie 2021 17:45:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#define NMAX 100003

using namespace std;

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

int dist[NMAX];
int visited[NMAX];

class Graph {

private:

	int nodes, edges, start_node, cnt_conex;
	vector<int>* adj;
	bool oriented = true;

private:

	void bfs() {
		queue<int> que;
		que.push(start_node);
		dist[start_node] = 1;

		while (!que.empty()) {
			int node = que.front();
			que.pop();
			for (int neighbor : adj[node]) {
				if (!dist[neighbor]) {
					dist[neighbor] = 1 + dist[node];
					que.push(neighbor);
				}
			}
		}
	}

	void dfs(int x = 1) {
		visited[x] = 1;
		for (int neighbor : adj[x]) {
			if (!visited[neighbor]) {
				dfs(neighbor);
			}
		}
	}

public:

	Graph(int nodes = 0, int edges = 0, int start_node = 0,bool oriented = true,int cnt_conex = 0) : 
		nodes(nodes), edges(edges),start_node(start_node),oriented(oriented), cnt_conex(cnt_conex){
		adj = new vector<int>[nodes+1];
	}
	~Graph() {
		delete[] adj;
	}

	void set_nodes(int n) {
		nodes = n;
	}
	void set_edges(int n) {
		edges = n;
	}
	void set_start_node(int n) {
		start_node = n;
	}

	void set_oriented(bool x) {
		oriented = x;
	}
	
	int get_nodes() {
		return nodes;
	}
	int get_edges() {
		return edges;
	}
	int get_start_node() {
		return start_node;
	}
	bool get_oriented() {
		return oriented;
	}

	void set_graph() {
		if (oriented) {
			for (int i = 1; i <= edges; i++) {
				int x, y;
				fin >> x >> y;
				adj[x].push_back(y);
			}
		}
		else {
			for (int i = 1; i <= edges; i++) {
				int x, y;
				fin >> x >> y;
				adj[x].push_back(y);
				adj[y].push_back(x);
			}
		}

	}
	void show_graph() {
		for (int i = 1; i <= nodes; i++) {
			cout << i << ":";
			for (int j = 0; j < adj[i].size(); j++) {
				cout << adj[i][j] << ' ';
			}
			cout << '\n';
		}
	}

	void get_distances() {
		bfs();
		for (int i = 1; i < nodes + 1; i++) {
			fout << dist[i] - 1 << ' ';
		}
	}

	void get_cnt_conex() {
		for (int i = 1; i <= nodes; i++) {
			if (!visited[i]) {
				cnt_conex++;
				dfs(i);
			}
		}
		fout << cnt_conex;
	}

};


int main()
{
	int N, M;

	fin >> N >> M;

	Graph g(N, M,0,false);
	g.set_graph();

	//g.get_distances();

	g.get_cnt_conex();

	return 0;

}