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 function. This is 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);
        }
    }
}

CodePudding user response：

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.

CodePudding user response：

Your implementation of the Depth first search is incorrect. 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;
    }
}