pastebin

pastebin

Paste Search Dynamic
Recent pastes
countComponents
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.HashMap;
  8. import java.util.HashSet;
  9. import java.util.List;
  10. import java.util.Map;
  11. import java.util.Set;
  12. import java.util.StringTokenizer;
  13.  
  14.  
  15. //import com.test.sec.Pair;
  16.  
  17.  
  18. public class Main
  19. {
  20.        
  21.         public static void main (string[] args) throws ioexception
  22.         {
  23.                 FastReader fr=new FastReader();
  24.                 int n=5;
  25.                 int [][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
  26.                 Map<Integer, Set<Integer>> map=buildGraph(edges);
  27.                 system.out.println(countComponents(n, map));
  28.         }
  29.  
  30.        
  31.        
  32.         private static Map<Integer, Set<Integer>> buildGraph(int[][] edges) {
  33.                 Map<Integer, Set<Integer>> map=new HashMap<>();
  34.                 for (int i = 0; i < edges.length; i++) {
  35.                         if(map.get(edges[i][0])==null) {
  36.                                 map.put(edges[i][0], new HashSet<>());
  37.                         }
  38.                         map.get(edges[i][0]).add(edges[i][1]);
  39.                         if(map.get(edges[i][1])==null) {
  40.                                 map.put(edges[i][1], new HashSet<>());
  41.                         }
  42.                         map.get(edges[i][1]).add(edges[i][0]);
  43.                 }
  44.                 return map;
  45.         }
  46.        
  47.         private static void dfs(Map<Integer, Set<Integer>> map, int node, int[] visited) {
  48.                 visited[node]=1;
  49.                 Set<Integer> set=map.get(node);
  50.                 for (integer integer : set) {
  51.                         if(visited[integer]==0) {
  52.                                 dfs(map, integer, visited);
  53.                         }
  54.                 }
  55.         }
  56.        
  57.         private static int countComponents(int n, Map<Integer, Set<Integer>> map) {
  58.                 int [] visited=new int[n];
  59.                 int count=0;
  60.                 arrays.fill(visited,0);
  61.                 for (int i = 0; i < visited.length; i++) {
  62.                         if(visited[i]==0) {
  63.                                 count++;
  64.                                 dfs(map, i, visited);
  65.                         }
  66.                 }
  67.                
  68.                 return count;
  69.         }
  70.        
  71.         private static boolean isStringHaveChar(string x, char c) {
  72.                 for (int i=0;i<x.length();i++) {
  73.                         if(x.charAt(i)==c) {
  74.                                 return true;
  75.                         }
  76.                 }
  77.                 return false;
  78.         }
  79.         private static int findSink(Set<Integer>[] edges) {
  80.                 // TODO Auto-generated method stub
  81.                 Set<Integer> searchedNums = new HashSet<>();
  82.                 int searchedNum=-1;
  83.                 for (int i = 0; i < edges.length; i++) {
  84.                         if (edges[i]==null) {
  85.                                 searchedNum=i;
  86.                                 searchedNums.add(i);
  87.                         }
  88.                 }
  89.                 if(searchedNums.size()==0||searchedNums.size()>1) {
  90.                         return -1;
  91.                 }
  92.                
  93.                 int i;
  94.                 for (i=0; i < edges.length; i++) {
  95.                         if(searchedNum != i) {
  96.                                 if(edges[i]!=null&&!edges[i].contains(searchedNum)) {
  97.                                         break;
  98.                                 }
  99.                         }
  100.                 }
  101.                 if(i==edges.length) {
  102.                         return searchedNum;
  103.                 }else {
  104.                         return -1;
  105.                 }
  106.                
  107.         }
  108.  
  109.         private static void printChain(int[] edges, int q) {
  110.                 if(q==-1) return;
  111.                 if(q>=edges.length) {
  112.                         system.out.println("Invalid number");
  113.                         return;
  114.                 }
  115.                 system.out.print(q+" ");
  116.                 printChain(edges,edges[q]);
  117.         }
  118.        
  119.         private static void printChainlen2(Set<Integer>[] edges) {
  120.                 for (int i = 0; i < edges.length; i++) {
  121.                         if(edges[i]==null) {
  122.                                 continue;
  123.                         }
  124.                         for (integer f:edges[i]) {
  125.                         if(edges[f]==null) {
  126.                                 continue;
  127.                         }
  128.                         for (integer f2:edges[f]) {
  129.                                 system.out.println(i+" "+f+" "+f2+" ");
  130.                                
  131.                             }                  
  132.                     }
  133.                 }
  134.                
  135.         }
  136.        
  137.        
  138. }
  139.  
  140. class recursionPractice {
  141.        
  142.         long fibb[]=new long[1000];
  143.        
  144.         long fib (int n) {
  145.                 if(n==0)
  146.                         return 0;
  147.                 if(n==1)
  148.                         return 1;
  149.                 long res=0;
  150.                 if(fibb[n-1]!=0)
  151.                         res+=fibb[n-1];
  152.                 else {
  153.                         fibb[n-1]=fib(n-1);
  154.                         res+=fibb[n-1];
  155.                 }
  156.                 if(fibb[n-2]!=0)
  157.                         res+=fibb[n-2];
  158.                 else {
  159.                         fibb[n-2]=fib(n-2);
  160.                         res+=fibb[n-2];
  161.                 }
  162.                 return res;
  163.         }
  164.        
  165.         int dr[]= {1,0,1};
  166.         int dc[]= {0,1,1};
  167.         int path_sum(int grid[][],int row,int col,int rows,int cols) {
  168.                 int sum=grid[row][col];
  169.                 if(row==rows-1&&col==cols-1) {
  170.                         return sum;
  171.                 }
  172.                 int max_idx=0,max_val=0;
  173.                 for (int d = 0; d < 3; d++) {
  174.                         int newRow=row+dr[d];
  175.                         int newCol=col+dc[d];
  176.                         if(newRow>=rows||newCol>=cols)
  177.                                 continue;
  178.                         if(max_val<grid[newRow][newCol]) {
  179.                                 max_val=grid[newRow][newCol];
  180.                                 max_idx=d;
  181.                         }
  182.                 }
  183.                 int newRow=row+dr[max_idx];
  184.                 int newCol=col+dc[max_idx];
  185.                 return sum + path_sum(grid, newRow, newCol, rows, cols);
  186.         }
  187.         boolean is_prime(int n, int cur_test_number) {
  188.                 if(n==2)
  189.                         return true;
  190.                 if(n<=1||n%2==0)
  191.                         return false;
  192.                 if(n==cur_test_number) // any number must be able to get divided by itself
  193.                         return true;
  194.                 if(n%cur_test_number==0)
  195.                         return false;
  196.                 return is_prime(n, cur_test_number+1);
  197.         }
  198.         int count_primes(int start,int end) {
  199.                 if(start>end) {
  200.                         return 0;
  201.                 }
  202.                 int x=is_prime(start,3)?1:0;
  203.                 return x+count_primes(start+1, end);
  204.         }
  205.         boolean is_prefix(string main,string prefix,int start) {
  206.                 if(start==prefix.length()) {
  207.                         return true;
  208.                 }
  209.                 if(main.charAt(start)==prefix.charAt(start)) {
  210.                         return is_prefix(main, prefix, start+1);
  211.                 }else {
  212.                         return false;
  213.                 }
  214.         }
  215.         boolean is_palindrome(int arr[],int start) {
  216.                 if(start<=arr.length-start) {
  217.                         return true;
  218.                 }
  219.                 if(arr[start-1]==arr[arr.length-start]) {
  220.                         return is_palindrome(arr, start-1);
  221.                 }else
  222.                         return false;
  223.         }
  224.         int prefix_sum(int arr[],int len,int n) {
  225.                 if(len==0) {
  226.                         return 0;
  227.                 }
  228.                 if(len>n) {
  229.                         return prefix_sum(arr,len-1,n);
  230.                 }else {
  231.                         return arr[len-1]+prefix_sum(arr,len-1,n);
  232.                 }
  233.         }
  234.         int suffix_sum(int arr[],int len,int n) {
  235.                 if(len==n-1) {
  236.                         return 0;
  237.                 }
  238.                 return arr[len-1]+suffix_sum(arr,len-1,n);
  239.         }
  240.         void right_max(int arr[],int len,int start) {
  241.                 if(start==arr.length)
  242.                         return;
  243.                 if(start==0) {
  244.                         right_max(arr, len-1,start+1);
  245.                         system.out.print(arr[len-1]+" ");
  246.                 }else {
  247.                         arr[len-1]=math.max(arr[len-1],arr[len]);
  248.                         right_max(arr, len-1,start+1);
  249.                         system.out.print(arr[len-1]+" ");
  250.                        
  251.                 }
  252.         }
  253.         void left_max(int arr[],int len) {
  254.                
  255.                 if(len==1) {
  256.                         system.out.print(arr[len-1]+" ");
  257.                         return;
  258.                 }
  259.                         left_max(arr, len-1);
  260.                         arr[len-1]=math.max(arr[len-1],arr[len-2]);
  261.                         system.out.print(arr[len-1]+" ");
  262.                
  263.         }
  264.         void accumulate_arr(int arr[],int len) {
  265.                
  266.                 if(len==1) {
  267.                         system.out.print(arr[len-1]+" ");
  268.                         return;
  269.                 }
  270.                
  271.                 accumulate_arr(arr, len-1);
  272.                 arr[len-1]+=arr[len-2];
  273.                 system.out.print(arr[len-1]+" ");
  274.                
  275.         }
  276.         void arr_increment(int arr[],int len) {
  277.                 if(len==0)
  278.                         return;
  279.                 arr_increment(arr, len-1);
  280.                 system.out.print(arr[len-1]+(len-1)+" ");
  281.         }
  282.         double avg(int arr[],int len) {
  283.                 if(len==0) {
  284.                         return arr[0];
  285.                 }
  286.                 return (arr[len-1] + (avg(arr, len-1)*(len-1)))/len;
  287.         }
  288.         int arr_sum(int arr[],int len) {
  289.                 if(len==0) {
  290.                         return 0;
  291.                 }
  292.                 return arr[len-1] + arr_sum(arr, len-1);
  293.         }
  294.         int arr_max(int arr[],int len) {
  295.                 if(len==0) {
  296.                         return 0;
  297.                 }
  298.                 return math.max(arr[len-1], arr_max(arr, len-1));
  299.         }
  300.         int lengthOf3nP1(int n) {              
  301.                 if(n==1) {
  302.                         return 1;
  303.                 }
  304.                 if(n%2!=0) {
  305.                         return 1+lengthOf3nP1(3*n+1);
  306.                 }
  307.                 else
  308.                         return 1+lengthOf3nP1(n/2);
  309.         }
  310.         int pow(int value,int power) {
  311.                 if(power==0) {
  312.                         return 1;
  313.                 }
  314.                 return value*pow(value,power-1);
  315.         }
  316. }
  317.  
  318. class FastReader {
  319.         //So useful function
  320.         public boolean isPrime(long n) {
  321.             if(n < 2) return false;
  322.             if(n == 2 || n == 3) return true;
  323.             if(n%2 == 0 || n%3 == 0) return false;
  324.             long sqrtN = (long)math.sqrt(n)+1;
  325.             for(long i = 6L; i <= sqrtN; i += 6) {
  326.                 if(n%(i-1) == 0 || n%(i+1) == 0) return false;
  327.             }
  328.             return true;
  329.         }
  330.         public boolean onlyZ(int[]ar) {
  331.                 for (int i = 0; i < ar.length; i++) {
  332.                         if (ar[i]!=0) {
  333.                                 return false;
  334.                         }
  335.                 }
  336.                 return true;
  337.         }
  338.         public boolean onlyO(int[]ar) {
  339.                 for (int i = 0; i < ar.length; i++) {
  340.                         if (ar[i]!=1) {
  341.                                 return false;
  342.                         }
  343.                 }
  344.                 return true;
  345.         }
  346.         public int getMedian(int a, int b, int c) {
  347.                 int arr[]= {a,b,c};
  348.                 arrays.sort(arr);
  349.                 return arr[1];
  350.         }
  351.     bufferedreader br;
  352.     bufferedwriter bw;
  353.     stringtokenizer st;
  354. //    FileOutputStream writer = new FileOutputStream("out.txt");  
  355. //    FileInputStream f = new FileInputStream("consecutive_cuts_chapter_2_validation_input.txt");
  356.  
  357. //    public FastReader() throws IOException {
  358. //      br = new BufferedReader(new InputStreamReader(f));
  359. //      bw = new BufferedWriter(new OutputStreamWriter(writer));
  360. //       }
  361.         public FastReader() {
  362.                
  363.             br = new bufferedreader(new inputstreamreader(system.in));
  364.         }
  365.  
  366.         public string next() {
  367.         while (st == null || !st.hasMoreElements()) {
  368.             try {
  369.                 st = new stringtokenizer(br.readLine());
  370.             } catch (ioexception e) {
  371.                 e.printStackTrace();
  372.             }
  373.         }
  374.         return st.nextToken();
  375.     }
  376.  
  377.     public int nextInt() {
  378.         return integer.parseInt(next());
  379.     }
  380.  
  381.     public long nextLong() {
  382.         return long.parseLong(next());
  383.     }
  384.  
  385.     public double nextDouble() {
  386.         return double.parseDouble(next());
  387.     }
  388.  
  389.     public float nextFloat() {
  390.         return float.parseFloat(next());
  391.     }
  392.  
  393.     // call next in each method to read the number or word and then to deal with it even as int or String, etc..
  394.     boolean Is_s(long[] a) {
  395.  
  396.         boolean b = false;
  397.         for (int i = 0; i < a.length; i++) {
  398.             if (a[i + 1] <= a[i]) {
  399.                 b = true;
  400.             }
  401.         }
  402.         if (b = true) {
  403.             return false;
  404.         } else {
  405.             return true;
  406.         }
  407.     }
  408.  
  409.    
  410.     public int upint(double d) {
  411.         if (math.round(d) < d) {
  412.             return (int) d + 1;
  413.         } else {
  414.             return (int) math.round(d);
  415.         }
  416.     }
  417.   //swap is working
  418.     public void swap(int[]a,int a1, int a2) {
  419.         int temp = a[a1];
  420.         a[a1] = a[a2];
  421.         a[a2] = temp;
  422.     }
  423.     public void swap(int[][]a,int a1,int b1, int a2,int b2) {
  424.         int temp = a[a1][b1];
  425.         a[a1][b1] = a[a2][b2];
  426.         a[a2][b2] = temp;
  427.     }
  428.     public string nextLine() {
  429.         string str = "";
  430.         try {
  431.             str = br.readLine();
  432.         } catch (ioexception e) {
  433.             e.printStackTrace();
  434.         }
  435.         return str;
  436.     }
  437.  
  438.     public int[] readInt(int size) {
  439.         int[] arr = new int[size];
  440.         for (int i = 0; i < size; i++) {
  441.             arr[i] = integer.parseInt(next());
  442.         }
  443.         return arr;
  444.     }
  445.  
  446.     public long[] readLong(int size) {
  447.         long[] arr = new long[size];
  448.         for (int i = 0; i < size; i++) {
  449.             arr[i] = long.parseLong(next());
  450.         }
  451.         return arr;
  452.     }
  453.  
  454.     public int[][] read2dArray(int rows, int cols) {
  455.         int[][] arr = new int[rows][cols];
  456.         for (int i = 0; i < rows; i++) {
  457.             for (int j = 0; j < cols; j++) {
  458.                 arr[i][j] = integer.parseInt(next());
  459.             }
  460.         }
  461.         return arr;
  462.     }
  463.  
  464.     public long[][] read2dArrayl(int rows, int cols) {
  465.         long[][] arr = new long[rows][cols];
  466.         for (int i = 0; i < rows; i++) {
  467.             for (int j = 0; j < cols; j++) {
  468.                 arr[i][j] = long.parseLong(next());
  469.             }
  470.         }
  471.         return arr;
  472.     }
  473.     public void sortStringsWith2chars(string[] names) {
  474.                
  475.                 string newNames[]=new string[names.length];
  476.                
  477.                 int idx=0;
  478.                 for (int i = 1; i <= 26*26; i++) {
  479.                                 for (int j2=0; j2 < names.length; j2++) {
  480.                                         if(((names[j2].charAt(0)-'a'+1)*26+names[j2].charAt(1)-'a'+1)-26==i) {
  481.                                                 newNames[idx++]=names[j2];
  482.                                         }
  483.                                 }
  484.                        
  485.                 }
  486.                 for (int i = 0; i < newNames.length; i++) {
  487.                         system.out.print(newNames[i]+" ");
  488.                 }
  489.                 system.out.println();;
  490.     }
  491. }
  492.  
Parsed in 0.393 seconds