Cod sursa(job #2789680)

Utilizator vali_27Bojici Valentin vali_27 Data 27 octombrie 2021 20:07:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

class Graph {
private:
	struct Edge {
		int x, y, cost;
		Edge(int x, int y, int cost = 0) : x(x), y(y), cost(cost) {}
	};

	struct Neighbour {
		int node, cost;
		Neighbour(int x, int cost = 0) : node(x), cost(cost) {}
	};

	std::vector<std::vector<Neighbour> >la;
	std::vector<Edge> edges;

	const int N_NODES;
	const int N_EDGES;

public:
	Graph(int N, int M) : N_NODES(N), N_EDGES(M) { la.resize(N + 1); }
	void getInfo();

	void addEdge(int from, int to, int cost = 0,bool isDirected = 0);

	std::vector<int> BFS(int start);

	int getComponentCount();
};

void Graph::addEdge(int from, int to, int cost, bool isDirected) {
	la[from].push_back({ to, cost });
	edges.push_back({ from, to, cost });

	if (!isDirected) {
		la[to].push_back({ from, cost });
	}
}

std::vector<int> Graph::BFS(int start) {
	std::vector<int> dist(N_NODES + 1, -1);
	dist[start] = 0;

	std::queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int top = q.front();
		q.pop();

		for (const Neighbour& x : la[top]) {
			if (dist[x.node] == -1) {
				dist[x.node] = dist[top] + 1;
				q.push(x.node);
			}
		}
	}
	return std::vector<int>(dist.begin() + 1, dist.end());
}

int Graph::getComponentCount() {
	std::stack<int> st;
	std::vector<bool> used(N_NODES + 1, false);
	int count = 0;
	
	for (int i = 1; i <= N_NODES; ++i) {
		if (!used[i]) {
			count++;

			// DFS
			st.push(i);
			while (!st.empty()) {
				int top = st.top();
				st.pop();
				used[top] = 1;
				
				for (const Neighbour& n : la[top])
					if (!used[n.node]) st.push(n.node);
			}
		}
	}

	return count;
}

void Graph::getInfo() {
	std::cout << "N: " << N_NODES << '\n';
	std::cout << "M: " << N_EDGES << '\n';
	for (int i = 1; i <= N_NODES; ++i) {
		std::cout << i << ": ";
		for (const Neighbour& x : la[i]) {
			std::cout << "(" << x.node << ", " << x.cost << ") ";
		}
		std::cout << '\n';
	}

	std::cout << "Edges: \n";
	for (const Edge& m : edges) {
		std::cout << m.x << " " << m.y << " " << m.cost << '\n';
	}
}

int main(){

	std::ifstream f("dfs.in");
	std::ofstream g("dfs.out");

	int N, M;
	f >> N >> M;

	Graph a(N, M);

	for (int i = 0; i < M; ++i) {
		int x, y;
		f >> x >> y;
		a.addEdge(x, y);
	}

	g << a.getComponentCount();
}