Find all connected components and their sizes in a graph

Question

I'm trying to find all connected components and their sizes in a graph. I don't know why, but the size is always 0. Maybe something is wrong in the method.

This is the problem that I am trying to solve. https://www.codechef.com/LRNDSA08/problems/FIRESC

public class B {
      static void dfs(int s, int v, boolean[] visited, ArrayList<ArrayList<Integer>> adj) {
        s++;
        visited[v] = true;
        for (int u : adj.get(v)) {
            if (!visited[u]) {
                dfs(s, u, visited, adj);
            }
        }
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder str = new StringBuilder();
        int t = sc.nextInt();
        for (int xx = 0; xx < t; xx++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                arr.add(new ArrayList<Integer>());
            }
            boolean[] visited = new boolean[n];
            Arrays.fill(visited, false);
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                a--;
                b--;
                arr.get(a).add(b);
                arr.get(b).add(a);
            }
            long ways = 1;
            int groups = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i])
                    continue;
                int size = 0;
                dfs(size, i, visited, arr);
                groups++;
                ways *= size;
                ways %= 1000000007;
            }
            System.out.println(groups + " " + ways);
        }
    }
}

Answer 1

You know size is passed as value and not as reference. So it won't get updated after you return from the call. One thing you could do is define a single element array like int[] size = new int[1];

and modify your dfs like:

  static void dfs(int[] s, int v, boolean[] visited, ArrayList<ArrayList<Integer>>  adj)  {
        s[0]++;
        visited[v] = true;
        for (int u : adj.get(v)) {
            if (!visited[u]) {
                dfs(s, u, visited, adj);
            }
        }
    }

Then your result will be in size[0] which you can use to update ways like ways *= size[0]

Or you could modify dfs to return size which is a cleaner way to get the size like below:

   static int dfs(int v, boolean[] visited, ArrayList<ArrayList<Integer>> adj) {
        visited[v] = true;
        int sz = 1;
        for (int u : adj.get(v)) {
            if (!visited[u]) {
                sz += dfs(u, visited, adj);
            }
        }
        return sz;
    }

Answer 2

And it seems like you have a misconception on how variables in Java work (see). Incrementing an int variable that resides on one lair of the stack would not affect a variable on another stack lair. That's why the size is always 0.

The following solution passes base test on CodeChef:

public class CountComponents {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
    
        for (int i = 0; i < testCases; i++) {
            EmployeeGraph graph = parseGraph(sc);
            graph.countComponentsAndComponentSizes();
        }
    }
    
    public static EmployeeGraph parseGraph(Scanner sc) {
        int employeeCount = sc.nextInt();
        int connectionsCount = sc.nextInt();
        
        boolean[][] adjacencyMatrix = new boolean[employeeCount][employeeCount];
        for (int i = 0; i < connectionsCount; i++) {
            int row = sc.nextInt() - 1;
            int col = sc.nextInt() - 1;
            adjacencyMatrix[row][col] = true;
            adjacencyMatrix[col][row] = true;
        }
        return new EmployeeGraph(adjacencyMatrix);
    }
}

class EmployeeGraph {
    public static final int BILLION_SEVEN = 1_000_000_007;
    private boolean[][] adjacencyMatrix;
    
    public EmployeeGraph(boolean[][] adjacencyMatrix) {
        this.adjacencyMatrix = adjacencyMatrix;
    }
    
    public void countComponentsAndComponentSizes() {
        boolean[] visited = new boolean[adjacencyMatrix.length];
        int componentCount = 0;
        int waysToChooseCaptain = 1;
        
        for (int row = 0; row < adjacencyMatrix.length; row++) {
            if (!visited[row]) {
                componentCount++;
                waysToChooseCaptain = (waysToChooseCaptain % BILLION_SEVEN) * dfs(visited, row);
            }
        }
    
        System.out.println(componentCount + " " + waysToChooseCaptain % BILLION_SEVEN);
    }
    
    public int dfs(boolean[] visited, int row) {
        visited[row] = true; // marking the current employee as visited
        
        int size = 1;        // this component consists at least from 1 employee
        
        for (int col = 0; col < adjacencyMatrix.length; col++) {
            if (adjacencyMatrix[row][col] && !visited[col]) {
                size += dfs(visited, col);
            }
        }
        
        return size;
    }
}