在圖中查找所有連接的組件及其大小

我試圖在圖表中找到所有連接的組件及其大小。我不知道為什么，但大小始終為0。可能是方法有問題。

這是我試圖解決的問題。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);
        }
    }
}

uj5u.com熱心網友回復：

您知道size作為值而不是作為參考傳遞。因此，在您從通話中回傳后，它不會得到更新。您可以做的一件事是定義一個單元素陣列，例如 int[] size = new int[1];

并修改您的 dfs，例如：

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

然后你的結果將是size[0]你可以用來更新ways的ways *= size[0]

或者您可以修改 dfs 以回傳大小。

uj5u.com熱心網友回復：

您似乎對 Java 中的變數如何作業有誤解（請參閱 參考資料）。遞增int駐留在堆疊的一個層上的變數不會影響另一個堆疊層上的變數。這就是為什么size總是0。

以下解決方案通過了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;
    }
}

標籤：爪哇 算法 数据结构 图论 深度优先搜索

上一篇：在Kotlin中，如果您每次都必須復制輸入來修改它，那么不可變引數如何影響空間復雜度？

下一篇：矩陣中的最大非負積