Make Depth First Search program more time 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.j

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.

Instead of having:

private ArrayList> adj; // List of List of Integers to
                                            // hold adjacency list
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;
    ArrayList adjacent;
 }
 private ArrayList 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 fringe = new Queue<>();
    Node start = g.getNode(j);
    start.mark();
    fringe.add(start);
    while(!fringe.isEmpty()){
        Node n = fringe.pop();
        for(Node a : n.adjacent){
            if(!a.isVisited()){
                a.mark();
                fringe.add(a);
            }
        }
    }
}

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 ());
   }

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> edges = new HashMap<>();

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

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

Hope this helps!

StackExchange Code Review Q#126823, answer score: 6