// compile-run-remove - "> g++ graph.cpp -std=c++11 -o gr && ./gr; rm ./gr"
#include <iostream>

class Graph {
#define MAX 1000

  struct IdSet {
    bool set[MAX];

    IdSet() {
      for (unsigned i = 0; i < MAX; i++) set[i] = false;
    }

    bool insert(unsigned value) { return value < MAX && (set[value] = true); }

    bool has(unsigned value) { return value < MAX && set[value]; }
  };

  struct Node {
    unsigned value, child_ids[MAX], size;

    Node(unsigned _value = 0) : value(_value), size(0) {}

    void add_child(unsigned child_id) {
      if (child_id < MAX && size < MAX) child_ids[size++] = child_id;
    }
  };

  Node nodes[MAX];
  int index_map[MAX];
  unsigned size;

 public:
  Graph() : size(0) {
    for (unsigned i = 0; i < MAX; i++) index_map[i] = -1;
  }

  void add_vertex(unsigned value) {
    if (size < MAX && value < MAX && index_map[value] == -1) {
      unsigned id = size++;
      nodes[id] = Node(value);
      index_map[value] = id;
    }
  }

  void add_edge(unsigned from_value, unsigned to_value) {
    if (from_value < MAX && to_value < MAX) {
      add_vertex(from_value);
      add_vertex(to_value);
      nodes[index_map[from_value]].add_child(index_map[to_value]);
    }
  }

  bool is_connected() {
    for (unsigned i = 0; i < size; i++)
      for (unsigned j = i + 1; j < size; j++) {
        IdSet ij_set, ji_set;
        if (!path_exists(i, j, ij_set) && !path_exists(j, i, ji_set))
          return false;
      }

    return true;
  }

 private:
  bool path_exists(unsigned from, unsigned to, IdSet &visited) {
    if (from == to) return true;
    if (visited.has(from)) return false;
    visited.insert(from);

    for (unsigned i = 0; i < nodes[from].size; i++)
      if (path_exists(nodes[from].child_ids[i], to, visited)) return true;

    return false;
  }
};

int main() {
  Graph connected;
  Graph disconnected;

  connected.add_edge(1, 2);
  connected.add_edge(2, 3);

  disconnected.add_edge(2, 1);
  disconnected.add_edge(2, 3);

  std::cout << "Should be true: " << connected.is_connected() << std::endl;
  std::cout << "Should be false: " << disconnected.is_connected() << std::endl;

  return 0;
}