Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static int sumOfSets(int n,List<String> edges){
- // contruct graph
- List<List<Integer>> graph = new ArrayList<>();
- for(int i=0;i<=n;i++){
- graph.add(new ArrayList<>());
- }
- for(String edge:edges){
- String[] nodes = edge.split(" ");
- int node1 = Integer.parseInt(nodes[0]);
- int node2 = Integer.parseInt(nodes[1]);
- graph.get(node1).add(node2);
- graph.get(node2).add(node1);
- }
- // find size of each connected component
- int sum = 0;
- List<Integer> sizes = new ArrayList<>();
- boolean[] visited = new boolean[n+1];
- for(int i=1;i<=n;i++){
- if(!visited[i]){
- int size = dfs(i,graph,visited);
- sizes.add(size);
- }
- }
- // print sizes
- for(int i=0;i<sizes.size();i++){
- double tmp = Math.log(sizes.get(i));
- // System.out.println(tmp);
- sum += tmp;
- }
- return sum;
- }
- public static int dfs(int node,List<List<Integer>> graph,boolean[] visited){
- visited[node] = true;
- int size = 1;
- for(int neighbour:graph.get(node)){
- if(!visited[neighbour]){
- size += dfs(neighbour,graph,visited);
- }
- }
- return size;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement