Graphs can be used for seemingly unconnected problems. Say the problem of cards which have numbers on both side and you try to create a continuous sequence of numbers using one side. This problem leads to problems in how to split a graph into connected subsets with cycles and connected subsets without cycles.
There are known algorithms to detect if the graph contains a circle. Here we modify it to find all nodes not-connected to circles. We add a Boolean array cyclic initiated as all false, meaning that no node is known to be connected to a circle.
Then we loop through nodes applied a usual algorithm to determine a circle skipping on nodes that are already known to be connected to a circle. Whenever we find a new node connected to a circle we propagate the property to all connected nodes skipping already designated as connected again.
Main function is a modification of DFS algorithm from article “Detect cycles in undirected graph“:
All nodes connected to a cycle are designated as such in a linear time.
The algorithm was applied to the following problem from the recent challenge “Germanium”, which was solved by about 3.5% of participants.
Suppose we have N cards (100000 >= N >= 1) and on both sides of the cards there is a number ( N are useless and can be discarded. In the same spirit, every car (n, m): n N allows us to put n upwards and ensured its presence in the sequence, while m is useless anyway.
If we have a card (n.n): n < N, it ensures that n can always be added to a continuous sequence that arrived to n-1.
If we have two identical cards (n, m) both n, m can be always added to a sequence if needed, just to put it on the opposite side.
Now we encode cards into a graph in the following way. The graph nodes are supposed to be numbered from 0 to N-1. Every node has a set of edges leading to is represented as a vector, initiated as an empty and overall set of edges is a vector of vectors of integers – edges (N).
(n, m) : n, m N – discarded.
(n, m): n N – add to the graph edge (n-1, n-1)
Now it is easy to understand that every cycle in the graph can be used for all nodes of the graph. A sample: (1, 2) (2, 5), (5, 1) – every number appears on two cards, just pass along the cycle and put any number once up and another time down:
(1, 2) – 1 up, 2 down
(2, 5) – 2 up, 5 down
(5, 1) – 5 up, 1 down
If any number already put on the upper side, every subsequent card that has the number must be out this number down, so another number can be shown on the upper side. In the graph, it means that any number connected by an edge to a number of cycles is free to be shown. The same is true for a card connected to the card connected to the cycle. So, any number/node that connected somehow to any cycle cannot provide any problem. Pairs of identical cards like (1, 2), (1, 2) also produce a small circle in the graph, the same is true for double cards, like 3, 3 it is a cycle of a node connected to itself.
All parts of the graph that are not connected to any cycle can be split in not connected smaller graphs. It is more or less obvious that any such fragment has a problematic number – the biggest in the fragment. We use a similar but much easier algorithm to find such fragments and all maximums in fragments. The least of it is Q – the smallest number that cannot be the end of the continuous coverage from the least numbers, the Q above.
In addition to the cyclic array, we add another array: visitedNonCyclic, meaning that this number already met while passing through a non-cycle fragment.
The maximum in the non-cycle fragment is extracted by recurrent calls to a function:
Please refer findMax() in below code. The graph creation is done in solution() of below code.
After the graph is created the solution just calls to isCyclic and then to:
// the main crux of the solution, see full code below graph.isCyclic(); int res = 1 + graph.GetAnswer();
The solution, which was inspired by the rather hard recent “Germanium 2018 Codility Challenge” and brought the gold medal.
Main Idea:
- Numbers are big, but we demand a continuous sequence from 1 to the last number,
but there are no more than 100 000 numbers. So, the biggest possible is really 100 000, take it as the first hypothesis - Due to the same considerations, the biggest number cannot be bigger than N (amount of numbers)
- We can also pass overall numbers and take the biggest which is NN. The result cannot be bigger than N or NN
- Taking this into account we can replace all cards like (x, 200 000) into (x, x). Both allow setting x upwards, x is not a problem thus.
- Cards with both numbers bigger that N or NN just ignored or disposed
- If there are cards with the same number on both sides it means that the number is always OK, cannot be the smallest problematic, so never the answer.
- If there are two identical cards like (x, y) and (y, x) it means that both x and y are not problematic and cannot be the answer
- Now we introduce the main BIG idea that we translate the set of cards into a graph. Vortices of the graph are numbered from 0 to M-1, where M is the last possible number (least of N, NN). Every node has some adjacent nodes, so the set of all edges is a vector of vectors of integers
- Every card like (x, y) with both numbers less or equal to M into edge x-1, y-1, so the first node gets an additional adjacent node and vice versa
- Some vortices will be connected to themselves due to cards like (3, 3). It is a loop case of size 1.
- Some vortices will be connected by two edges or more if there are identical cards. It is a loop of size 2.
- Loops of sizes 1 and 2 have numbers that cannot be of any problem. But now we realize that the same is the case of a cycle of any length. For example, cards are 2, 3; 3, 4; 4, 10; 10, 2; All their numbers have no problem, just put 2, 3, 4, 10 to the upper side. The downside will have 3, 4, 10, 2.
- Now if we have a card x, y and we know that x is guaranteed already in another place, we can put this card x down, y up and ensure that the y is in the resulting sequence.
- So, if any card is connected to a cycle by an edge, it cannot present a problem since the cycle is all OK, so this number is also OK.
- Thus if there is an interconnected subset of nodes of a graph which contains a cycle, all vortices cannot present any problem.
So, we can apply one of the known algorithms to find loops like in the article “Detect cycle in an undirected graph” with an addition of propagation - We can also designate all nodes in the graph that are connected to a cycle, cycled[]. And we can propagate the property
Just start with some in a cycle, set it as a cycled, then pass over it’s adjacent skipping the cycled and calling the same function on the adjacent. - Using a combination of the known algorithm to detect cycles in an undirected graph with skipping on cycled already and propagating the property “connected to a cycle”, we find all nodes connected to cycles. All such nodes are safe, they cannot be a problem
- But remain nodes not connected to any cycle, their problem can be simplified but cutting into separated graphs which have no common edges or nodes.
- But what to do with them? It can be a linear branch or branches that cross one another. All nodes are different.
- With some last effort, one can understand that any such set has only one problematic number – maximum of the set. It can be proven, paying attention that crosses only makes thing better, but the maximum stays still.
- So we cut all non-cycled into connected separated entities and find the maximum in every one.
- Then we find the minimum of them and this is the final answer!
Examples:
Input : A = [1, 2, 4, 3] B = [1, 3, 2, 3]
Output : 5.
Because the cards as they are provide 1, 2, 3, 4 but not 5.Input : A = [4, 2, 1, 6, 5] B = [3, 2, 1, 7, 7],
Output: 4.
Because you can show 3 or 4 by the first card but not both 3 and 4. So, put 3, while 1 and 2 are by the following cards.Input : A = [2, 3], B = [2, 3]
Output : 1. Because 1 is missing at all.
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N);
Implementation:
C++
#include <algorithm>#include <vector>using namespace std;class Graph {private: int V; // No. of vertices vector<vector<int> > edges; // edges grouped by nodes bool isCyclicUtil(int v, vector<bool>& visited, int parent); vector<bool> cyclic; vector<int> maxInNonCyclicFragments; int findMax(int v); vector<bool> visitedNonCyclic; void setPropagateCycle(int v);public: Graph(int V); // Constructor void addEdge(int v, int w); // to add an edge to graph // returns true if there is a cycle and // also designates all connected to a cycle bool isCyclic(); int getSize() const { return V; } int GetAnswer();};Graph::Graph(int V){ this->V = V; edges = vector<vector<int> >(V, vector<int>()); visitedNonCyclic = cyclic = vector<bool>(V, false);}void Graph::addEdge(int v, int w){ edges[v].push_back(w); edges[w].push_back(v);}void Graph::setPropagateCycle(int v){ if (cyclic[v]) return; cyclic[v] = true; for (auto i = edges[v].begin(); i != edges[v].end(); ++i) { setPropagateCycle(*i); }}bool Graph::isCyclicUtil(int v, vector<bool>& visited, int parent){ if (cyclic[v]) return true; // Mark the current node as visited visited[v] = true; // Recur for all the vertices edgesacent to this vertex vector<int>::iterator i; for (i = edges[v].begin(); i != edges[v].end(); ++i) { // If an edgesacent is not visited, then // recur for that edgesacent if (!visited[*i]) { if (isCyclicUtil(*i, visited, v)) { setPropagateCycle(v); return true; } } // If an edgesacent is visited and not parent // of current vertex, then there is a cycle. else if (*i != parent) { setPropagateCycle(v); return true; } if (cyclic[*i]) { setPropagateCycle(v); return true; } } return false;}bool Graph::isCyclic(){ // Mark all the vortices as not visited // and not part of recursion stack vector<bool> visited(V, false); // Call the recursive helper function // to detect cycle in different DFS trees bool res = false; for (int u = 0; u < V; u++) // Don't recur for u if it is already visited{ if (!visited[u] && !cyclic[u]) { if (isCyclicUtil(u, visited, -1)) { res = true; // there was return true originally visited = vector<bool>(V, false); } } return res;}int Graph::findMax(int v){ if (cyclic[v]) return -1; if (visitedNonCyclic.at(v)) return -1; int res = v; visitedNonCyclic.at(v) = true; for (auto& u2 : edges.at(v)) { res = max(res, findMax(u2)); } return res;}int Graph::GetAnswer(){ // cannot be less than, after extract must add 1 int res = V; for (int u = 0; u < V; u++) { maxInNonCyclicFragments.push_back(findMax(u)); } for (auto& u : maxInNonCyclicFragments) { if (u >= 0) res = min(res, u); } return res;}int solution(vector<int>& A, vector<int>& B){ const int N = (int)A.size(); const int MAX_AMOUNT = 100001; vector<bool> present(MAX_AMOUNT, false); for (auto& au : A) { if (au <= N) { present.at(au) = true; } } for (auto& au : B) { if (au <= N) { present.at(au) = true; } } int MAX_POSSIBLE = N; for (int i = 1; i <= N; i++) { if (false == present.at(i)) { MAX_POSSIBLE = i - 1; break; } } Graph graph(MAX_POSSIBLE); for (int i = 0; i < N; i++) { if (A.at(i) > MAX_POSSIBLE && B.at(i) > MAX_POSSIBLE) { continue; } int mi = min(A.at(i), B.at(i)); int ma = max(A.at(i), B.at(i)); if (A.at(i) > MAX_POSSIBLE || B.at(i) > MAX_POSSIBLE) { graph.addEdge(mi - 1, mi - 1); } else { graph.addEdge(mi - 1, ma - 1); } } graph.isCyclic(); int res = 1 + graph.GetAnswer(); return res;}// Test and driver#include <iostream>void test(vector<int>& A, vector<int>& B, int expected, bool printAll = false){ int res = solution(A, B); if (expected != res || printAll) { for (size_t i = 0; i < A.size(); i++) { cout << A.at(i) << " "; } cout << endl; for (size_t i = 0; i < B.size(); i++) { cout << B.at(i) << " "; } cout << endl; if (expected != res) cout << "Error! Expected: " << expected << " "; else cout << "Expected: " << expected << " "; } cout << " Result: " << res << endl;}int main(){ vector<int> VA; vector<int> VB; int A4[] = { 1, 1, 1, 1, 1 }; int B4[] = { 2, 3, 4, 5, 6 }; VA = vector<int>(A4, A4 + 1); VB = vector<int>(B4, B4 + 1); test(VA, VB, 2, true); int A0[] = { 1, 1 }; int B0[] = { 2, 2 }; VA = vector<int>(A0, A0 + 2); VB = vector<int>(B0, B0 + 2); test(VA, VB, 3); int A[] = { 1, 2, 4, 3 }; int B[] = { 1, 3, 2, 3 }; VA = vector<int>(A, A + 4); VB = vector<int>(B, B + 4); test(VA, VB, 5); int A2[] = { 4, 2, 1, 6, 5 }; int B2[] = { 3, 2, 1, 7, 7 }; VA = vector<int>(A2, A2 + 5); VB = vector<int>(B2, B2 + 5); test(VA, VB, 4); int A3[] = { 2, 3 }; int B3[] = { 2, 3 }; VA = vector<int>(A3, A3 + 2); VB = vector<int>(B3, B3 + 2); test(VA, VB, 1); return 0;} |
1 2 Expected: 2 Result: 2 Result: 3 Result: 5 Result: 4 Result: 1
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
