Speeding up this Tarjan's algorithm

Question

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

1. Number of Strongly connected components
2. Size of the largest strongly connected component

3. (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<Integer>[] graph;
    int[] lowlink;
    boolean[] used;
    List<Integer> stack;
    List<List<Integer>> components;
    int maxSize = 0;

    private int getMaxSize() {
        return maxSize;
    }

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

        for (int u = 0; u < n; u++)
            if (!used[u])
                dfs(u);

        return components;
    }

    void dfs(int u) {
        lowlink[u] = time++;
        used[u] = true;
        stack.add(u);
        boolean isComponentRoot = true;

        for (int v : graph[u]) {
            if (!used[v])
                dfs(v);
            if (lowlink[u] > lowlink[v]) {
                lowlink[u] = lowlink[v];
                isComponentRoot = false;
            }
        }

        if (isComponentRoot) {
            List<Integer> component = new ArrayList<Integer>();
            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));
        try {
            String s = read.readLine();
            String[] parts = s.split(" ");
            String part1 = parts[0];
            String part2 = parts[1];
            N = Integer.parseInt(part1);
            P = Integer.parseInt(part2);
        } catch (IOException e) {
            e.printStackTrace();
        }

        int counter = 0;
        @SuppressWarnings("unchecked")
        List<Integer>[] g = new List[N];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<Integer>();
        }

        while (counter < P) {
            String s;
            try {
                s = read.readLine();
                String[] parts = s.split(" ");
                String part1 = parts[0];
                String part2 = parts[1];

                int x = Integer.parseInt(part1);
                int y = Integer.parseInt(part2);

                g[x - 1].add(y - 1);

            } catch (IOException e) {
                e.printStackTrace();
            }
            counter++; 
        }

        Tarjan t = new Tarjan();

        List<List<Integer>> components = t.scc(g);

        System.out.println(components.size());


        /* Check note 1 below that explains this part of the algorithm */

        int isolatedScc = 0;
        int contains = 1;
        for (List<Integer> sccList : components) {
            int i;
            contains = 1;
            for (i = 0; i < g.length; i++) {
                if (sccList.contains(i))
                    continue;
                else {
                    for (Integer nodeInScc : sccList) {
                        List<Integer> nodesConnectedToTheNodesInSCC = g[nodeInScc];
                        if (nodesConnectedToTheNodesInSCC.contains(i)) {
                            contains = 0;
                            break;
                        }
                    }

                }

            }

            if (contains == 1)
                isolatedScc++;

        }

        System.out.println(t.getMaxSize());
        System.out.println(isolatedScc);

    }
}

To test the program, simply run it. It will wait for your input. The first two number you input will define the number of nodes and the number of connection. The rest of the lines define the connections between nodes.

5 4
1 2
1 3
2 3
4 1

In this example we have: number of nodes: 5. Number of connections between nodes: 4 The rest of the lines are the 4 connections between the 5 nodes.

Note 1:

This is the part of the algorithm that I think slows it down a lot. Basically what I'm doing here is, for every node in the SCCS, check any node that isn't inside that SCC and check any of them has a connection to any node outside of the SCC (that is, a path between that node to the node outside of the SCC). If so, then break. If it reaches the end of the loop, than that situation doesn't happen. So increase a counter

Is there any possible way I can speed up this thing? I compiled it with jdk1.6.

Answer 1

Generics

Java Generics will not accept the declaration: List<Integer>[] You cannot have an array of a generically typed component. There are ways to make it neater, but, you should be using List<List<Integer>> 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).