Advertisement
unknown_0711

Untitled

Dec 28th, 2022
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. class Edge {
  4. int src;
  5. int nbr;
  6.  
  7. Edge(int src, int nbr) {
  8. this.src = src;
  9. this.nbr = nbr;
  10. }
  11. }
  12. class Solution{
  13. public static int perfectStudents(int vtces, ArrayList<Edge>[] graph){
  14. boolean[] visited = new boolean[vtces];
  15. ArrayList<ArrayList<Integer>> comps = new ArrayList<>();
  16. for(int v = 0; v < vtces; v++){
  17. if(visited[v] == false){
  18. ArrayList<Integer> comp = new ArrayList<>();
  19. gcc(graph, v, visited, comp);
  20. comps.add(comp);
  21. }
  22. }
  23.  
  24. int count = 0;
  25. for(int i = 0; i < comps.size(); i++){
  26. for(int j = i + 1; j < comps.size(); j++){
  27. count += comps.get(i).size() * comps.get(j).size();
  28. }
  29. }
  30. return count;
  31. }
  32. public static void gcc(ArrayList<Edge>[] graph, int src, boolean[] visited, ArrayList<Integer> comp) {
  33. comp.add(src);
  34. visited[src] = true;
  35. for (Edge e : graph[src]) {
  36. if (!visited[e.nbr]) {
  37. gcc(graph, e.nbr, visited, comp);
  38. }
  39. }
  40. }
  41. }
  42. public class Main {
  43. public static void main(String[] args) throws Exception {
  44. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  45.  
  46. int n = Integer.parseInt(br.readLine());
  47. int k = Integer.parseInt(br.readLine());
  48.  
  49. int vtces = n;
  50. ArrayList<Edge>[] graph = new ArrayList[vtces];
  51. for (int i = 0; i < vtces; i++) {
  52. graph[i] = new ArrayList<>();
  53. }
  54.  
  55. int edges = k;
  56. for (int i = 0; i < edges; i++) {
  57. String[] parts = br.readLine().split(" ");
  58. int v1 = Integer.parseInt(parts[0]);
  59. int v2 = Integer.parseInt(parts[1]);
  60. graph[v1].add(new Edge(v1, v2));
  61. graph[v2].add(new Edge(v2, v1));
  62. }
  63. System.out.println(Solution.perfectStudents(n, graph));
  64. }
  65.  
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement