graph_representations.cpp

#include <cassert>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <vector>

using Incidence = std::bitset<2>;

template <typename T>
class Matrix {
	std::vector<T> array; // std::vector<bool> is compact
public:
	size_t rows;
	const size_t columns;
	Matrix(size_t columns_, size_t rows_=0): array(columns_ * rows_), rows(rows_), columns(columns_) {}
	decltype(auto) operator() (size_t row, size_t column) { return array[row * columns + column]; }
	auto operator() (size_t row, size_t column) const { return array[row * columns + column]; }
	auto begin() const { return array.begin(); }
	auto end() const { return array.end(); }

	/* For dynamically adding edges to transposed incidence matrix.
	I don't ask the number of edges in advance.
	Trying to convert an adjacency matrix representing undirected graph
	to incidence matrix results in duplicate edges. */
	void append(const std::vector<T>& rows) {
		assert(rows.size() % columns == 0);
		// array.append_range(rows);
		array.insert(array.end(), rows.begin(), rows.end());
		this->rows += rows.size() / columns;
	}
};

template <typename T>
std::ostream& operator<<(std::ostream& out, const Matrix<T>& matrix) {
	auto width = out.width();
	for (size_t i = 0; i < matrix.rows; i++) {
		for (size_t j = 0; j < matrix.columns; j++) {
			out << std::setw(width) << matrix(i, j) << ' ';
		}
		out << '\n';
	}
	return out;
}

int main() {
	std::string line;
	unsigned vertices;
	std::cout << "Number of vertices? ";
	std::cin.exceptions(std::ios_base::badbit | std::ios_base::failbit | std::ios_base::eofbit);
	std::cin >> vertices;

	std::cout << "Directed [y/n]? ";
	std::getline(std::cin, line); // nothing else works...
	bool directed = tolower(std::cin.get()) != 'n';
	std::getline(std::cin, line); // nothing else works...
	const Incidence IN  = directed ? 0x2 : 0x3;
	const Incidence OUT = directed ? 0x1 : 0x3;

	Matrix<unsigned> adjacency(vertices, vertices);
	Matrix<Incidence> incidence(vertices);

	std::vector<Incidence> edge;
	for (unsigned vertex = 0, neighbour; vertex < vertices; vertex++) {
		std::cout << "Neighbours of vertex " << vertex << " (space-separated)? ";
		std::getline(std::cin, line);
		std::istringstream iss(line);
		while (iss >> neighbour) {
			edge.assign(vertices, 0);
			edge[vertex] |= OUT;
			edge[neighbour] |= IN;
			incidence.append(edge);
			adjacency(vertex, neighbour)++;
			adjacency(neighbour, vertex) += !directed && vertex != neighbour;
		}
	}

	std::cout
		<< "\nAdjacency matrix:\n" << std::setw(2) << adjacency
		<< "\nTransposed incidence matrix:\n" << incidence;

	std::cin.exceptions(std::ios_base::goodbit);
	do {
		unsigned vertex;
		std::cout << "\nQuery a vertex? ";
		if (!(std::cin >> vertex)) break;
		std::cout << "Connected to: ";
		for (unsigned i = 0; i < vertices; i++)
			if (adjacency(vertex, i))
				std::cout << i << ' ';
		std::cout << "\nReachable from: ";
		for (unsigned i = 0; i < vertices; i++)
			if (adjacency(i, vertex))
				std::cout << i << ' ';
	} while (true);
}

skazad.zig

////usr/bin/env zig run "$0" -- "$@"; exit
const std = @import("std");
// C++'s `std::bitset`'s size needs to be known during compilation.
const BitSet = std.bit_set.DynamicBitSetUnmanaged;

fn readInt() !u32 {
    var buffer = [_]u8{0} ** 8;
    const stdin = std.io.getStdIn().reader();
    const raw = try stdin.readUntilDelimiter(&buffer, '\n');
    return std.fmt.parseInt(u32, raw, 10);
}

pub fn cycles(allocator: std.mem.Allocator, graph: []const u32) !u32 {
    var result: u32 = 0;
    var just_visited: BitSet = try BitSet.initEmpty(allocator, graph.len);
    defer just_visited.deinit(allocator);
    var prev_visited: BitSet = try BitSet.initEmpty(allocator, graph.len);
    defer prev_visited.deinit(allocator);

    for (1..graph.len) |i| {
        var j = i;
        while (!just_visited.isSet(j)) {
            if (prev_visited.isSet(j)) break;
            just_visited.set(j);
            j = graph[j];
        } else result += 1;
        prev_visited.setUnion(just_visited);
        just_visited.unsetAll();
    }

    return result;
}

test cycles {
    const allocator = std.testing.allocator;
    try std.testing.expectEqual(2, cycles(allocator, &[_]u32{ 0, 2, 1, 2, 4 }));
}

pub fn main() !void {
    const N = try readInt();

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    const allocator = arena.allocator();
    defer arena.deinit();

    var graph = try allocator.alloc(u32, N + 1);

    for (1..N + 1) |i| {
        graph[i] = try readInt();
    }

    const stdout = std.io.getStdOut().writer();
    const result = try cycles(allocator, graph);
    try stdout.print("{}\n", .{result});
}