SHARE
TWEET

Untitled

a guest Nov 12th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import javafx.util.Pair;
  2.  
  3. import java.io.File;
  4. import java.io.FileNotFoundException;
  5. import java.io.PrintWriter;
  6. import java.util.*;
  7.  
  8. public class Roads {
  9.     static int N;
  10.     static int M;
  11.     static boolean[] visit;
  12.  
  13.  
  14.     public static void main(String[] args) throws FileNotFoundException {
  15.         Scanner in = new Scanner(new File("input.txt"));
  16.         PrintWriter pw = new PrintWriter(new File("output.txt"));
  17.         N = in.nextInt();
  18.         M = in.nextInt();
  19.         visit = new boolean[N];
  20.         Vector<Vector<Integer>> list = new Vector<>();
  21.         for(int i = 0; i<N; i++)
  22.             list.add(new Vector<>());
  23.         Queue<Integer> vertices = new LinkedList<>();
  24.  
  25.         for(int i = 0; i < M ; i++)
  26.         {
  27.             int n = in.nextInt()-1;
  28.             int m = in.nextInt()-1;
  29.             list.get(n).add(m);
  30.             list.get(m).add(n);
  31.         }
  32.         int numberOfComponents = 0;
  33.         for(int index = 0; index<N; index++)
  34.         {
  35.             if(!visit[index])
  36.             {
  37.                 vertices.add(index);
  38.                 visit[index] = true;
  39.                 while ( !vertices.isEmpty())
  40.                 {
  41.                     int ind = vertices.poll();
  42.                     for (int i=0; i<list.get(ind).size(); i++)
  43.                     {
  44.                         if(!visit[list.get(ind).get(i)]){
  45.                             vertices.add(list.get(ind).get(i));
  46.                             visit[list.get(ind).get(i)] = true;
  47.                         }
  48.                     }
  49.                 }
  50.                 numberOfComponents++;
  51.             }
  52.         }
  53.         pw.print(numberOfComponents-1);
  54.         pw.close();
  55.     }
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top