Advertisement
jbn6972

Untitled

Nov 29th, 2023
586
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.39 KB | None | 0 0
  1. public static int sumOfSets(int n,List<String> edges){
  2.         // contruct graph
  3.  
  4.         List<List<Integer>> graph = new ArrayList<>();
  5.         for(int i=0;i<=n;i++){
  6.             graph.add(new ArrayList<>());
  7.         }
  8.  
  9.         for(String edge:edges){
  10.             String[] nodes = edge.split(" ");
  11.             int node1 = Integer.parseInt(nodes[0]);
  12.             int node2 = Integer.parseInt(nodes[1]);
  13.             graph.get(node1).add(node2);
  14.             graph.get(node2).add(node1);
  15.         }
  16.  
  17.         // find size of each connected component
  18.         int sum = 0;
  19.         List<Integer> sizes = new ArrayList<>();
  20.         boolean[] visited = new boolean[n+1];
  21.         for(int i=1;i<=n;i++){
  22.             if(!visited[i]){
  23.                 int size = dfs(i,graph,visited);
  24.                 sizes.add(size);
  25.             }
  26.         }
  27.  
  28.         // print sizes
  29.  
  30.         for(int i=0;i<sizes.size();i++){
  31.  
  32.             double tmp = Math.log(sizes.get(i));
  33.             // System.out.println(tmp);
  34.             sum += tmp;
  35.         }
  36.  
  37.         return sum;
  38.        
  39.     }
  40.  
  41.     public static int dfs(int node,List<List<Integer>> graph,boolean[] visited){
  42.         visited[node] = true;
  43.         int size = 1;
  44.         for(int neighbour:graph.get(node)){
  45.             if(!visited[neighbour]){
  46.                 size += dfs(neighbour,graph,visited);
  47.             }
  48.         }
  49.         return size;
  50.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement