Speeding up this Tarjan's algorithm

I'm implementing an algorithm that traverses a graph of nodes (after a given input) and outputs 3 things:

• Number of Strongly connected components

• Size of the largest strongly connected component

-
(And here I think is the step that slows down my algorithm) The number of SCC's that are ONLY connected between them.

This means that, for every node in that SCC, none of them has a path to other nodes outside the SCC. Only other nodes outside of the SCC connect to them. Like they are isolated inside the SCC.

If this isn't clear, please tell me so I can rephrase.

Here's the code and how to use it:

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Tarjan {

int time;
static int N;
static int P;
List[] graph;
int[] lowlink;
boolean[] used;
List stack;
List> components;
int maxSize = 0;

private int getMaxSize() {
return maxSize;
}

public List> scc(List[] graph) {
int n = graph.length;
this.graph = graph;
lowlink = new int[n];
used = new boolean[n];
stack = new ArrayList();
components = new ArrayList>();

for (int u = 0; u lowlink[v]) {
lowlink[u] = lowlink[v];
isComponentRoot = false;
}
}

if (isComponentRoot) {
List component = new ArrayList();
while (true) {
int k = stack.remove(stack.size() - 1);
component.add(k);
lowlink[k] = Integer.MAX_VALUE;
if (k == u)
break;
}
int size = component.size();
if (size > this.maxSize)
maxSize = size;

components.add(component);
}
}

public static void main(String[] args) {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

Generics

Java Generics will not accept the declaration: List[] You cannot have an array of a generically typed component. There are ways to make it neater, but, you should be using List> in a general case.

Variable names

Variables like n, t, N, P, u, etc. are not helpful. They make the code hard to read and understand. Use descriptive variable names. It helps. A lot!

Variable Scope

Static non-final variables are almost always a sign of bad ObjectOriented design:

static int N;
static int P;

These should be final instance variables on your class, or something, but setting them in the main method and using them in an instance method is backward. It also means you can only have one (working) instance of your graph.

Object Structure

Your class is not a class.... it is a procedural mashup. You have a procedural system for setting up your graph (which is contained in two Lists), and then you create a TarJan instance for no particular reason other than that the methods are not static.... You then delegate some work to the TarJan instance, pull the results back in to the main method, and then procedurally complete the process.

This is a poor design.

The graph should be self-contained in a single instance object, and its data structure should all be internal.

Java Functions should also have a single-responsibility defined in the function: do one thing, and one thing well.

Your main method should look more like:

public void main (String[] args) {
    Graph graph = buildGraphFromStdIn();
    System.out.println("Component Count: " + graph.getComponentCount());
    System.out.println("Largest SCC Size: " + graph.getLargestComponentSize());
    ....
}

Performance

Performance should normally come after functionality. At the moment, your code needs a fix-up with respect to conventions and style. As you go through the code mobing things in to neat compartments, you will likely find the performance improves simply because you structure things better, and notice where things go wrong.

At the moment, it is pretty hard to see what is happening, so I am not particularly inclined to dig though it and guess what's going wrong (performance wise).

StackExchange Code Review Q#44599, answer score: 2