Advertisement
unknown_0711

Untitled

Jan 4th, 2023
19
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.40 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. class Main {
  4. public static void main(String args[]) throws IOException {
  5. BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
  6. int N = Integer.parseInt(read.readLine());
  7.  
  8. ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
  9.  
  10. for(int i=0; i<N; i++)
  11. {
  12. String S[] = read.readLine().split(" ");
  13. ArrayList<Integer> temp = new ArrayList<>();
  14. for(int j=0; j<N; j++)
  15. temp.add(Integer.parseInt(S[j]));
  16. adj.add(temp);
  17. }
  18.  
  19. Solution ob = new Solution();
  20. System.out.println(ob.components(adj,N));
  21. }
  22. }
  23.  
  24. class Solution {
  25. void dfs(ArrayList<ArrayList<Integer>> M, int[] visited, int i)
  26. {
  27. for (int j = 0; j < M.size(); j++)
  28. {
  29. if (i!=j && M.get(i).get(j) == 1 && visited[j] == 0)
  30. {
  31. visited[j] = 1;
  32. dfs(M, visited, j);
  33. }
  34. }
  35. }
  36.  
  37. int components(ArrayList<ArrayList<Integer>> adj, int N) {
  38.  
  39. int[] visited = new int[adj.size()];
  40. int count = 0;
  41. for (int i = 0; i < adj.size(); i++)
  42. {
  43. if (visited[i] == 0)
  44. {
  45. dfs(adj, visited, i);
  46. count++;
  47. }
  48. }
  49. return count;
  50. }
  51. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement