CareerCup

Test

Test

This can be modeled as a graph with an intersection as a node. Each road is an edge, so that a two-way road between an intersection and another is 2 directed edges between the 2 nodes.

To find a pair of intersections that have a unique path between them, we need to do a 2-pass BFS starting at a random node. First pass we note down all the nodes that have been visited through 2 or more paths (say via a 'visited' field, that we ++ the second time a node is visited) and then in the second pass, we see if there is a node that got visited == 1. We can return on the first such node that we visit.

Time complexity: O(|V| + |E|), extra space O(|V|).

EDIT 1: I don't think it's best to model each lane as a directed edge between 2 intersections, since that means a 2-way road will always create a cycle. What we can do is instead model the intersections as nodes, and a generic "road" as an edge. Each edge can then have a property "1-way" or "2-way", along with a "sourceNode" property (in case it's a 1-way).

Additionally, when we do the BFS, we only traverse the "1-way" edges, since otherwise, there's always a 2'nd route that you can create by just looping within 2-nodes.

Killedsteel's solution is a good starting point, but I think that we have to start the search from every node because it could happen that for example we randomly select a node which has no leaving edges.

Below I present a solution which looks for all intersection pairs with only one path between them because that way it is easier to check the solution, but you could also stop the search as soon as at least one pair is found.

It is not specified, but I supposed that going through a cycle several times does not count as separate paths, thus there is on_stack check (as well as for the sake of not entering an infinite loop).

There is a path counter for each node. As soon as counter reaches two there is no need to consider that node anymore. We could omit that check and get all paths, but that would worsen the worst case performance, especially in dense graphs. When increasing counter from one to two it is necessary to continue with the DFS in order to update counters of the children.

For each starting node we visit edges leaving a certain node at most twice, which leads to the time complexity of O(VE). Space complexity is O(V), if we exclude the resulting vector.

Here is a working C++11 solution with two samples. I could have moved the check to parent's DFS call and thus spare additional functions call, but I find it more readable this way.

#include <iostream>
#include <vector>
#include <memory>
#include <utility>
#include <algorithm>

class Intersection {
public:
  Intersection(int id) : id_(id) {}

  const std::vector<std::weak_ptr<Intersection>>& get_neighbours() const {
    return neighbours_;
  }

  void add_neighbour(std::weak_ptr<Intersection> neighbour) {
    neighbours_.push_back(neighbour);
  }

  int get_id() const {
    return id_;
  }

private:
  int id_;
  std::vector<std::weak_ptr<Intersection>> neighbours_;
};

class CityMap {
public:
  std::shared_ptr<Intersection> get_intersection(int id) {
    return intersections_[id];
  }

  const std::shared_ptr<Intersection> get_intersection(int id) const {
    return intersections_[id];
  }

  void add_intersection(std::shared_ptr<Intersection> intersection) {
    intersections_.push_back(intersection);
  }

  std::size_t size() const {
    return intersections_.size();
  }

private:
  std::vector<std::shared_ptr<Intersection>> intersections_;
};

void extract_pairs(const std::vector<int>& ways, int from, std::vector<std::pair<int, int>>* res_ptr) {
  std::vector<std::pair<int, int>>& res = *res_ptr;
  for(int to = 0; to < ways.size(); ++to) {
    if(1 == ways[to]) res.emplace_back(from, to);
  }
}

void dfs(const Intersection& curr, std::vector<int>* ways_ptr, std::vector<bool>* on_stack_ptr) {
  int curr_id = curr.get_id();
  std::vector<int>& ways = *ways_ptr;
  std::vector<bool>& on_stack = *on_stack_ptr;
  if(ways[curr_id] >= 2 || on_stack[curr_id]) return;

  on_stack[curr_id] = true;
  //ways[curr_id] += ways[parent];
  ++ways[curr_id];

  for(const std::weak_ptr<Intersection> inters_ptr : curr.get_neighbours()) {
    dfs(*(inters_ptr.lock()), ways_ptr, on_stack_ptr);
  }

  on_stack[curr_id] = false;
}

std::vector<std::pair<int, int>> find_single_ways(const CityMap& cm) {
  std::vector<std::pair<int, int>> res;
  std::vector<int> ways(cm.size());
  std::vector<bool> on_stack(cm.size());

  for(int i = 0; i < cm.size(); ++i ) {
    std::fill(std::begin(ways), std::end(ways), 0);
    std::fill(std::begin(on_stack), std::end(on_stack), false);
    on_stack[i] = true;

    for(const std::weak_ptr<Intersection> inters_ptr : cm.get_intersection(i)->get_neighbours())
      dfs(*(inters_ptr.lock()), &ways, &on_stack);
 
    
    extract_pairs(ways, i, &res);
  }

  return std::move(res);
}

int main() {
  CityMap cm;
  
  cm.add_intersection(std::make_shared<Intersection>(0));
  cm.add_intersection(std::make_shared<Intersection>(1));
  cm.add_intersection(std::make_shared<Intersection>(2));
  cm.add_intersection(std::make_shared<Intersection>(3));
  cm.add_intersection(std::make_shared<Intersection>(4));
  cm.add_intersection(std::make_shared<Intersection>(5));
  cm.add_intersection(std::make_shared<Intersection>(6));

  cm.get_intersection(0)->add_neighbour(cm.get_intersection(1));
  cm.get_intersection(0)->add_neighbour(cm.get_intersection(2));
  cm.get_intersection(1)->add_neighbour(cm.get_intersection(3));
  cm.get_intersection(2)->add_neighbour(cm.get_intersection(1));
  cm.get_intersection(3)->add_neighbour(cm.get_intersection(2));
  cm.get_intersection(3)->add_neighbour(cm.get_intersection(4));
  cm.get_intersection(4)->add_neighbour(cm.get_intersection(5));
  cm.get_intersection(4)->add_neighbour(cm.get_intersection(6));
  cm.get_intersection(6)->add_neighbour(cm.get_intersection(5));

  /*cm.get_intersection(0)->add_neighbour(cm.get_intersection(1));
  cm.get_intersection(0)->add_neighbour(cm.get_intersection(4));
  cm.get_intersection(0)->add_neighbour(cm.get_intersection(6));
  cm.get_intersection(1)->add_neighbour(cm.get_intersection(2));
  cm.get_intersection(2)->add_neighbour(cm.get_intersection(3));
  cm.get_intersection(2)->add_neighbour(cm.get_intersection(5));
  cm.get_intersection(4)->add_neighbour(cm.get_intersection(2));
  cm.get_intersection(5)->add_neighbour(cm.get_intersection(4));
  cm.get_intersection(5)->add_neighbour(cm.get_intersection(6));*/

  auto res = find_single_ways(cm);

  for(auto r : res)
    std::cout << "From " << r.first << " to " << r.second << std::endl;


  return 0;
}