CareerCup

struct Edge
{
	int from;
	int to;
};

bool CheckRestrictedPath(const unordered_map<int, int>& edges, const vector<Edge>& R)
{
	for (const auto& e : R)
	{
		int start = e.from;
		while (true)
		{
			auto it = edges.find(start);
			if (it == edges.end())
				break;

			if (it->second == e.to)
				return false;

			start = it->second;
		}
	}

	return true;
}

vector<Edge> AddEdges(const vector<Edge>& M, const vector<Edge>& K)
{
	vector<Edge> ret;
	unordered_map<int, int> edge_map;

	for (const auto& e : M)
	{
		edge_map[e.from] = e.to;
		if (!CheckRestrictedPath(edge_map, K))
		{
			auto it = edge_map.find(e.from);
			if (it != edge_map.end())
				edge_map.erase(it);

			continue;
		}

		ret.emplace_back(e);
	}

	return ret;
}

#include <vector>
#include <iostream>
using namespace std;

class QuickUnion {
private:
    vector<int> id_;
    vector<int> sz_;
    vector<vector<int>> k_;

public:
    QuickUnion(int n, vector<vector<int>> k) {
        for (int i = 0; i < n; i++) {
            id_.push_back(i);
            sz_.push_back(1);
        }
        k_ = k;
    }

    bool connect(int i, int j) {
        i -= 1, j -= 1;

        if (i < 0 || j < 0 || i >= id_.size() || j >= id_.size())
            return false;

        int ri = root(i);
        int rj = root(j);

        if (ri == rj) return true;

        int oldRi = id_[ri];
        bool discard = false;
        id_[ri] = rj;
        for (auto p : k_) {
            if (connected(p[0], p[1])) {
                discard = true;
                break;
            }
        }
        id_[ri] = oldRi;
        if (discard) return false;

        if (sz_[ri] < sz_[rj]) {
            id_[ri] = rj;
            sz_[rj] += sz_[ri];
        } else {
            id_[rj] = ri;
            sz_[ri] += sz_[rj];
        }

        return true;
    }

    bool connected(int i, int j, bool flatten = true) {
        return root(i-1, flatten) == root(j-1, flatten);
    }

private:
    int root(int i, bool flatten = true) {
        if (i < 0 || i >= id_.size()) return -1;
        while (i != id_[i]) {
            if (flatten) id_[i] = id_[id_[i]];
            i = id_[i];
        }
        return i;
    }
};

int main() {
    int n = 4;
    vector<vector<int>> k = {
        {1, 4}
    };
    vector<vector<int>> m = {
        {1, 2}, {2, 3}, {3, 4}
    };

    QuickUnion q(4, k);

    for (auto e : m) {
        if (!q.connect(e[0], e[1])) {
            cout << "Discarding {" << e[0] << ", " << e[1] << "}" << endl;
        }
    }

    return 0;
}

#include <vector>
#include <iostream>
using namespace std;

class QuickUnion {
private:
    vector<int> id_;
    vector<int> sz_;
    vector<vector<int>> k_;

public:
    QuickUnion(int n, vector<vector<int>> k) {
        for (int i = 0; i < n; i++) {
            id_.push_back(i);
            sz_.push_back(1);
        }
        k_ = k;
    }

    bool connect(int i, int j) {
        i -= 1, j -= 1;

        if (i < 0 || j < 0 || i >= id_.size() || j >= id_.size())
            return false;

        int ri = root(i);
        int rj = root(j);

        if (ri == rj) return true;

        int oldRi = id_[ri];
        bool discard = false;
        id_[ri] = rj;
        for (auto p : k_) {
            if (connected(p[0], p[1])) {
                discard = true;
                break;
            }
        }
        id_[ri] = oldRi;
        if (discard) return false;

        if (sz_[ri] < sz_[rj]) {
            id_[ri] = rj;
            sz_[rj] += sz_[ri];
        } else {
            id_[rj] = ri;
            sz_[ri] += sz_[rj];
        }

        return true;
    }

    bool connected(int i, int j, bool flatten = true) {
        return root(i-1, flatten) == root(j-1, flatten);
    }

private:
    int root(int i, bool flatten = true) {
        if (i < 0 || i >= id_.size()) return -1;
        while (i != id_[i]) {
            if (flatten) id_[i] = id_[id_[i]];
            i = id_[i];
        }
        return i;
    }
};

int main() {
    int n = 4;
    vector<vector<int>> k = {
        {1, 4}
    };
    vector<vector<int>> m = {
        {1, 2}, {2, 3}, {3, 4}
    };

    QuickUnion q(4, k);

    for (auto e : m) {
        if (!q.connect(e[0], e[1])) {
            cout << "Discarding {" << e[0] << ", " << e[1] << "}" << endl;
        }
    }

    return 0;
}

void add(const vector<pair<int, int> > &M, const vector<pair<int, int> > &K)
{
  unordered_map<int, bool> restricted;
  unordered_map<int, vector<int> > graph;

  // add restricted vertices to a unordered_map for quick lookup
  for (const auto &path : K) {
    restricted[path.first] = true;
    restricted[path.second] = true;
  }

  for (const auto &edge : M) {
    if (restricted[edge.first] && restricted[edge.second]) {
      // edge completes a path, cannot be added
      continue;
    }

    // add the edge to the graph
    graph[edge.first].push_back(edge.second);
    graph[edge.second].push_back(edge.first);

    if (restricted[edge.first] || restricted[edge.second]) {
      // if either vertex is connected to a path endpoint,
      // mark all reachable points from this edge as restricted
      markRestricted(graph, edge.first, restricted);
    }
  }
}

void markRestricted(const unordered_map<int, vector<int> > &graph, int vertex,
                                    unordered_map<int, bool> &restricted)
{
  // Start a DFS from vertex and mark vertices as restricted
  unordered_set<int> visited;
  stack<int> stk;
  stk.push(vertex);
  while (!stk.empty()) {
    int v = stk.top();
    stk.pop();
    if (visited.find(v) != visited.end()) continue;
    restricted[v] = true;
    visited.insert(v);
    for (int next : graph[v]) {
      stk.push(next);
    }
  }
}

The problem can be solved using DSU. DSU will give if a path exists between 2 nodes in almost constant time. Hence the problem can be solved O(K.M)