# Make Depth First Search program more efficient

This is a problem from programming contest. The original problem can be found here on hackerearth.com.

In the first line there is one integer T denoting the number of test cases. Description of T test cases follow. Each one have two integers N and K given in the first line denoting the number of variables and the number of relations between them for this test case. All variables are represented by integers in range [1, N]. K lines follow. Each of them is of the form "x1 R x2" where x1 and x2 are integers representing variables and R is either "=" or "!=" and denotes the kind of relation between these variables.

Output format:

Output exactly T lines. In i-th of them, output the answer to the i-th test case.

Constraints:

T <= 10

1 <= N, K <= 10^6

Sum of N in one test file does not exceed 10^6

Sum of K in one test file does not exceed 10^6

SAMPLE INPUT

2
2 2
1 = 2
1 != 2
3 2
1 = 2
2 != 3


SAMPLE OUTPUT

NO
YES


Explanation

There are 2 test cases. In the first one, you cannot fulfill all relations, because equality and inequality of two number cannot be both true. In the second one, you can for example assign 10 to 1 and 2 and 20 to 3 in order to fulfill all relations.

My approach:

Let G be a graph where input variables are vertices and there is an edge between a and b if and only if there in relation a = b in the input. Then if we compute connected components of G, all variables belonging to the same component must have the same value assigned to them. On the other hand, any two variables which belong to different connected components can have assigned different values.

Now, having computed connected components of G, we can easily decide if we can satisfy all input relations. Just iterate over all inequalities from the input, and if for any inequality a != b, a and b are in the same connected component, the answer is NO, otherwise, the answer is YES.

Graph.java

class Graph {
private int v; // Total vertices of Graph
private ArrayList<ArrayList<Integer>> adj; // List of List of Integers to
private boolean[] marked; // Array to hold visited nodes
int[] id; // Array to hold group number
int count;

public Graph(int v) {
this.v = v;
marked = new boolean[v];
id = new int[v];
for (int i = 0; i < v; i++) {
}
}

public int getv() {
return v;
}

public void addEdge(int v, int w) {
}

}

public boolean isVisited(int v) {
return marked[v];
}

public void mark(int v) {
marked[v] = true;
}

public boolean connected(int v, int w) {
return id[v] == id[w];
}
}


Relation.java

public class Relation {

public static class Pair {
int i, j;

public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}

public static void main(String[] args) throws IOException {
System.in));
String delims = " ";
String[] tokens;
while (t-- > 0) {
List<Pair> notequal = new ArrayList<Pair>();
int n = Integer.parseInt(tokens[0]);
int k = Integer.parseInt(tokens[1]);
Graph G = new Graph(n);
for (int i = 0; i < k; i++) {
if (tokens[1].equals("=")) {
Integer.parseInt(tokens[2]) - 1);

} else
Integer.parseInt(tokens[2]) - 1));

}

for (int j = 0; j < n; j++) {
if (!G.isVisited(j)) {
dfs(G, j);
G.count++;
}
}

// System.out.println(G);
boolean flag = true;
for (Pair pair : notequal) {
int x1 = pair.i;
int x2 = pair.j;
if (G.connected(x1, x2)) {
flag = false;
break;
}
}

if (flag)
System.out.println("YES");
else
System.out.println("NO");
}
}

private static void dfs(Graph g, int j) {

g.mark(j);
g.id[j] = g.count;
for (int w : g.adj(j)) {
if (!g.isVisited(w)) {
dfs(g, w);
}
}
}
}


How to make this code more efficient?

• Efficient in terms of time. – Santosh Apr 29 '16 at 17:16
• @DarthGizka: looks like it's an entry-level challenge on hackerearth.com. Probably no twists involved. ;) – Pieter Witvoet May 4 '16 at 15:13
• @DarthGizka: eh, you're right. :) I overlooked that edge-case. Bummer. – Pieter Witvoet May 6 '16 at 13:30
• @Santosh: the grace period on your bounty is running out in a few hours and you haven't accepted an answer yet... Emily's answer gives you style and a few ideas that may or may not have measurable impact on performance, and my answer shows how to cut the fluff and push performance to the limit. I guess at least two people are interested to know whether you prefer form or function, theory or practice... If you found neither answer helpful, could you tell us what you need? – DarthGizka May 7 '16 at 7:20

# Style

I understand that this is a quick and dirty piece of code to earn some points on some code-challenge website. I will still offer some comments on style.

private int v;


This variable is never used outside of the constructor, in fact it is almost always shadowed by a method parameter. As such I would remove this member and the accessor getv() which isn't used either.

Variable shadowing is something I detest and find makes code much harder to read. I would recommend that you get into a habit of avoiding shadowing.

private ArrayList<ArrayList<Integer>> adj; // List of List of Integers to
private boolean[] marked; // Array to hold visited nodes
int[] id; // Array to hold group number
int count;


You could do :

class Node{
private int id;
private boolean marked;
}
private ArrayList<Node> nodes;


which makes it a bit easier to reason about the state of the class.

There are other nitpicks but I'm not going to go into that as I'm sure you're aware of most of them already.

# Performance - Function call overhead in DFS

I haven't benchmarked so take this with a grain of salt. The only place that I see that could be done faster is the dfs method. Currently it is a recursive method that recurses at most N times. If you instead chose to implement an iterative BFS you could get rid of a lot of the function call overhead in what I believe is the most time consuming part of the code.

Edit: Fixed performance where a node could appear twice in the fringe

Something like this (untested pseudo java-ish code):

private static void bfs(Graph g, int j){
Queue<Node> fringe = new Queue<>();
Node start = g.getNode(j);
start.mark();
while(!fringe.isEmpty()){
Node n = fringe.pop();
if(!a.isVisited()){
a.mark();
}
}
}
}


# Performance - Unnecessary work creating adjacency lists

Here you create a bunch of adjacency lists to represent the connectivity of the graph, depending on the input, some (or all) may never be used:

   for (int i = 0; i < v; i++) {
}


There are some ways that you can avoid this:

## Use a connectivity matrix

Create a VxV boolean matrix, edges where edges[v*V+w] is true if v and k are connected and false otherwise and V is the number of vertices in the graph. Note that this matrix is symmetric and you only ever need to compute the upper right half.

Note that you need to adjust your dfs() function so that you iterate over one row or column in the matrix depending on how you structure it.

Now that the original question has been corrected from N < 106 to N < 10^6 this is no longer feasible.

## Use a HashMap

Create a map that contains the adjacency lists that are created when needed:

Map<Integer, ArrayList<Integer>> edges = new HashMap<>();

public void addEdge(int v, int w) {
ArrayList<Integer> vList = edges.get(v);
if(null == vList){
vList = new ArrayList<>();
edges.put(vList);
}

ArrayList<Integer> wList = edges.get(w);
if(null == wList){
wList = new ArrayList<>();
edges.put(wList);
}
}


Hope this helps!

• While function call overhead can lead to significant performance drops, I find that it usually it's not worth the effort to get rid of recursive functions; my experience is not main java, though, and here things may be different (experienced comments welcome). – Clearer May 4 '16 at 10:33
• @Clearer when the compiler can eliminate the recursion through Tail Call Optimization or when the work performed in the function body is large compared to function call overhead then you are correct but in this case I believe that neither of those are true. – Emily L. May 4 '16 at 10:42
• As I said, my experience is not mainly in Java but in other languages. If it's easy to get rid of the recursion (especially if someone has already provided a solution for you), you should ofc just do it; it's a free optimization which doesn't depend on the compiler -- even if it's slight. Even with recursive functions which the compiler cannot optimize away, my experience is that it makes little difference if the implementation is manually optimized away. As always, it depends highly on the compiler (and flags) and the particular implementation in question. – Clearer May 4 '16 at 11:15
• Making dfs iterative is relevant for another reason as well: the website that hosts this challenge contains a test-case that pretty much guarantees a stack-overflow. – Pieter Witvoet May 4 '16 at 22:06

(tl;dr: linked lists via array; 50 ms for 1 million items; code at end of article)

The chosen approach is well suited to the task, and on the conceptual level it is very clean and lean. The equivalence relations are represented as edges in a graph, and connected component discovery efficiently identifies the sets of equivalent items and tags their members.

It is just on the practical level that things get just as messy as they would be if one chose to model sets directly:

public Graph(int v) {
// ...
// ...
for (int i = 0; i < v; i++) {
}
}


Therein lies a major issue - you are creating up to 10^6 lists just in case they might be needed, and this can eat up a big chunk of your allotted time.

Moreover, a maliciously crafted input file can contain up to 10^6 equivalences (assuming that you don't want to slow things down by essentially superfluous checks), so that changing the logic to creating the adjacency lists on demand does not change worst-case behaviour.

This is essentially the same problem one would face when choosing to model sets directly via the set-like structures offered by one's language libraries. Also, for good programming challenge sites it can be taken as given that all major types of problematic inputs will actually occur.

Hence it is best to implement the adjacency lists as linked lists here. During the input phase this gives you O(1) insertion (since you simply prepend to whatever is already there), and during the sweep you walk the list element by element anyway.

With modern runtimes it should be efficient enough to simply new the nodes, so that no extra effort for efficient allocation would be needed. This is different from C/C++, where one would probably allocate a big array of them at the start of a test case and dole them out incrementally, so that all of them can be discarded afterwards en bloc with a single free() or delete[]. If this approach were chosen in Java or C# then it would be imperative to keep the blocks of nodes small enough that they do not get classified as 'large objects', which would cause problems with the garbage collector. This might be less of a concern for a programming challenge but in long-running code it could get nasty.

I concur with all respondents who recommended an iterative sweep instead of recursive function calls. Above-mentioned input file would likely blow the call stack to smithereens. Use an explicit stack or ArrayList<> for storing nodes to be visited later while you are chasing the links of a given list.

There is no need to have separate fields for component id and a 'visited' flag, if you check the 'emptiness' of a component id during the sweep before assigning it. The key to speed and simplicity is slimming the code via measures like this, to reduce it to its essentials.

Note: Emily's advice to use an array of structs instead of a struct of arrays is sound, because it often leads to cleaner code that is easier to understand.

However, when performance is critical then it can be better to have separate arrays. This can have a major performance impact, since Java does not have value-type structs yet; in the present case you can achieve a five-fold speedup by using a two-dimensional array (which is poor man's array of value-type structs) or two separate arrays, instead of stuffing class references into an array as suggested by Emily.

Sometimes it can be beneficial to have separate arrays for reasons of CPU cache performance, especially if different phases of processing have markedly different access frequencies and patterns. In the present case that is unlikely to cause marked speed differences, unless one were coding in assembler or C/C++.

In the light of the comments it seems indicated to explain the linked list angle in a bit more detail. For easier benchmarking I've factored out the code that computes the equivalence classes (a.k.a. 'connected component ids') from the pairs of equal items. I'm showing the code in a hashish language because I don't have a Java environment handy but I don't want to post code that is not fully tested. I've removed all production-quality noise like assertions and nulling of unused references, in order to make the code more readable.

First, the Node class:

class Node
{
public int target;
public Node next;

public Node (int target, Node next)
{
this.target = target;
this.next = next;
}
}


And now the code for computing the equivalence classes. Apart from the use of linked lists and iterative sweeping with an explicit stack instead of recursive function calls it is based on the same algorithm as Santosh's solution. It is just packaged differently.

static int[] equivalence_classes_for_pairs (IEnumerable<Tuple<int,int>> pairs, int max_n)
{
var list_heads = new Node[max_n + 1];  // +1 because of index base 0

foreach (var pair in pairs)
{
}

var equivalence_classes = new int[list_heads.Length];  // equivalence class for i, or 0 if unknown
var more_chains = new Stack<Node>();
int class_count = 0;

for (int i = 1; i <= max_n; ++i)
{

if (node == null || equivalence_classes[i] != 0)
continue; // nothing there, or already visited

int current_class = ++class_

equivalence_classes[i] = current_class;

while (true)
{
for ( ; node != null; node = node.next)
{
if (equivalence_classes[node.target] == 0)  // not visited yet
{
equivalence_classes[node.target] = current_class;
}
}

if (more_chains.Count == 0)
break;

node = more_chains.Pop();
}
}

for (int i = 1; i <= max_n; ++i)
if (equivalence_classes[i] == 0)
equivalence_classes[i] = ++class_count;

return equivalence_classes;
}


On my machine this takes about 250 ms for 10^6 pairs. Separate measurements show that the bulk of that time is spent in new Node(); creating 2 million nodes took about 200 ms whereas pulling them from a free list took only 5 ms. This suggests a possible improvement if the cost of creating the nodes can be amortised over several test cases. I cooked up a few functions that could be used as drop-in replacements in the above code:

static Node free_list = create_free_list(2 * MAX_N);

static Node create_free_list (int n)
{
for (int i = 0; i < n; ++i)
}

static Node new_Node (int target, Node next)
{
Node node = free_list;
free_list = node.next;
node.target = target;
node.next   = next;
return node;
}

static Node free_and_get_next (Node node)
{
Node next = node.next;
node.next = free_list;
free_list = node;
return next;
}


With this, the changes in the earlier functions are limited to replacing new Node with new_Node, and node = node.next with node = free_and_get_next(node). However, I'm not showing the code here because the final code that implements linked lists by indexing into an array is so much simpler, cleaner, and even slightly faster.

Using preallocation via a free list reduces the running time from 250 ms to 50 ms. For a single call the 200 ms for creating the free list with 2 million nodes would have to be added, resulting in a net change of zero, but if there is more than one call then the cost of node creation is spread and overall time taken is reduced. A similar argument can be made for ArrayList, where creation is roughly five times as costly as clearing.

However, the task description gives 10^6 as the total limit over all test cases in an input file (up to 10 per file). This makes it less likely that the cost of creating 2 million nodes can be be spread enough to result in a major improvement.

An alternative that is worth exploring is to use an array to achieve fast and efficient allocation. I.e. nodes[i, 0] would be equivalent to Node.target and nodes[i, 1] would be equivalent to Node.next. An alternative would be to have separate targets[] and links[] arrays, for a slight improvement in readability. In any case an allocated counter would be initialised to 0 at the beginning of the procedure and henceforth always point at the next free slot. No freeing of slots ('list nodes') is necessary.

The time for a million pairs is 50 ms, and the code is actually a bit simpler than the code using pointers (since the allocation management overhead consists only of incrementing a counter, no free list management is necessary). This makes the array variant of linked lists the overall winner, and 50 ms looks fairly good for Java/C#.

Here's a rendering that uses a value-type struct instead of separate array dimensions, for readability. In Java only two 'plain' array versions are applicable but the principle remains the same; the struct definition won't be needed there but in exchange the function body gets a bit more verbose.

struct ListNode
{
public int target;
public int next;

public ListNode (int target, int next)
{
this.target = target;
this.next = next;
}
}


Note: since ListNode is a value-type, operator new does not allocate anything on the heap. The compiler simply puts an anonymous variable on the stack and initialises the structure fields as dictated by the constructor. On the native code level this should be virtually the same as code that uses separate array dimenions (at most a teeny bit less efficient). The version show here simply gives readable names to the two array dimensions, in a manner of speaking, and it minimises the number of array indexings.

static int[] equivalence_classes_for_pairs_v7 (IEnumerable<Tuple<int,int>> pairs, int max_n)
{
var list_heads = new int[max_n + 1];  // +1 because of index base 0
var list_nodes = new ListNode[1 + 2 * pairs.Count()];
int allocated = 1;  // slot 0 is used as sentinel, and slot index 0 signifies 'empty'

foreach (var pair in pairs)
{

}

var equivalence_classes = new int[list_heads.Length];  // 0 if not assigned yet
int class_count = 0;
var more_chains = new Stack<int>();

for (int i = 1; i <= max_n; ++i)
{
if (equivalence_classes[i] != 0)
continue;

int current_class = ++class_count;

equivalence_classes[i] = current_class;
more_chains.Push(0);  // sentinel

for (int p = list_heads[i]; p != 0; p = more_chains.Pop())
{
while (p != 0)
{
ListNode node = list_nodes[p];

if (equivalence_classes[node.target] == 0)  // not visited yet
{
equivalence_classes[node.target] = current_class;
}

p = node.next;
}
}
}

return equivalence_classes;
}


P.S.: Thanks to Santosh for bringing this nice problem to our attention - it taught me a lot about sets, linked lists, and efficient bulk allocation in Java/C#. Plus, it is always a pleasure in itself to take a solution idea for a well-confined problem, to strip it to its essentials and then make the code sing. Apologies to Emily for any unnecessary rudeness on my part - her advice is sound and important. At first glance, style and maintainability might seem a non-issue for the throw-away code of a coding challenge submission. However, we all do these challenges to learn something that stays, and at the end of the day Emily's lessons are bound to be much more generally applicable than aspects of my particular solution to this particular problem.

• Also the suggestion to use LinkedList doesn't make sense. In the DFS search OP is iterating over the adjacency list, you suggest iterating over a LinkedList rather than iterating through an ArrayList? Appending to an ArrayList is amortized O(1) and is just as fast a LinkedList in fact, my benchmark shows that ArrayList is slightly faster. – Emily L. May 5 '16 at 19:24
• @Emily: N and K are limited to 10^6, have a look for yourself. And I wasn't suggesting using a LinkedList, I was talking about a linked list, e.g. var v = new Node[MAX_N] where Node has a next field of type Node (i.e. a pointer to another node). Repeat your benchmark to see the constant factors dropped by asymptotics can make a big difference in practice, and that putting lipstick on a pig won't make it fly. Also, the 'amortised' bit should give you bit of worry, in a performance-critical situation. – DarthGizka May 5 '16 at 19:48
• The original question reads 106, so I suppose that is a copy paste fail. I repeated my benchmark, with 10^6 entries ArrayList is avg 34% faster not to mention that the speed of the 'amortised' ArrayList is much more even than the O(1) insertion LinkedList. This pig is flying well and good. – Emily L. May 5 '16 at 19:57
• @Emily: On my system, creating 10^6 ArrayList<int> and adding 1 element to each takes about half a second; the time limit for the task is 1 second (but there's a bit more stuff to do than just creating the lists, including the parsing of input which often causes TLE all on its own in Java and C#). – DarthGizka May 5 '16 at 20:04
• Okay I see that we're talking apples and oranges here. I presume you mean to create some kind of disjoint set data structure using linked lists? If that is the case then I suppose that would work. – Emily L. May 5 '16 at 20:19