ways-to-represent-graphs.cpp

/*
	Ways to Represent Graphs
	Charles (@c650)

	Showing how to represent _unweighted_ graphs
	in C++.
*/
#include <iostream>
#include <vector>

struct edge {
	int a,b;
};

int main(void) {

	/* the number of nodes, n*/
	int n;
	std::cin >> n;

	/* number of edges, m*/
	int m;
	std::cin >> m;

	/* imagine we are taking in some number n edges represented as node pairs a,b*/

	/*
		Here's an adjacency matrix, a vector of N vectors of N bools.
		adjacency_matrix[i][j] is true if there is an edge directly between nodes i and j.

		If the graph is _undirected_ adjacency_matrix[i][j] and adjacency_matrix[j][i]
		must have the same value.
	*/
	std::vector<std::vector<bool>> adjacency_matrix(n, std::vector<bool>(n, false));

	/*
		This is our adjacency list, a vector of N vectors.
		But each element of the list (e.g., adjacency_list[i])
		is an _empty_ vector.
	*/
	std::vector<std::vector<int>>  adjacency_list(n);

	/*
		A vector of edges. Useful in some cases when you care
		more about the edges than the nodes they connect.
	*/
	std::vector<edge> edges(m);

	int a,b; /* variables for our edge pairs (input of a and b should be in [0,n) */

	/* read in `m` edges */
	for (int i = 0; i < m; ++i) {
		std::cin >> a >> b;

		/* what always happens */
		adjacency_matrix[a][b] = true;
		adjacency_list[a].push_back(b);

		/* ONLY do this part if the graph is undirected. */
		adjacency_matrix[b][a] = true;
		adjacency_list[b].push_back(a);

		/* also store the edge */
		edges[i] = { a , b };
	}

	return 0;
}

std::bad_alloc called when initializing a graph G(8,8)