Advertisement
pascallius

Untitled

Dec 3rd, 2022
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.33 KB | Source Code | 0 0
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. // ADDITIONAL IMPORTS ARE NOT ALLOWED
  4.  
  5. class Main {
  6.   public static void main(String[] args) {
  7.     // Uncomment the following two lines if you want to read from a file
  8.     In.open("public/small.in");
  9.     Out.compareTo("public/small.out");
  10.  
  11.     int n = In.readInt(); //number of vertices
  12.     int edges = In.readInt();
  13.     int x = In.readInt();
  14.     int y = In.readInt();
  15.     ArrayList<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>(n);
  16.     ArrayList<ArrayList<Integer>> G_r = new ArrayList<ArrayList<Integer>>(n);
  17.  
  18.     for (int i = 0; i < n; i++) {
  19.       G.add(new ArrayList<Integer>());
  20.       G_r.add(new ArrayList<Integer>());
  21.     }
  22.    
  23.     for (int i = 0; i < edges; i++) {
  24.       int src = In.readInt();
  25.       int trg = In.readInt();
  26.       G.get(src).add(trg);
  27.       G_r.get(trg).add(src);
  28.     }
  29.  
  30.     Out.println(countInBetween(n, G,G_r, x, y));
  31.    
  32.     // Uncomment this line if you want to read from a file
  33.     In.close();
  34.   }
  35.  
  36.   public static int countInBetween(int n, ArrayList<ArrayList<Integer>> G,ArrayList<ArrayList<Integer>> G_r, int x, int y) {
  37.     boolean[] G_mark = new boolean[n];
  38.     boolean[] G_mark_r = new boolean[n];
  39.     ArrayList<Integer> list_forward = new ArrayList<Integer>();
  40.     ArrayList<Integer> list_backward = new ArrayList<Integer>();
  41.     BFS(x,G,G_mark,list_forward);
  42.     BFS(y,G_r,G_mark_r,list_backward);
  43.    
  44.     list_forward.retainAll(list_backward);
  45.     return list_forward.size();
  46.    
  47.   }
  48.  
  49.   public static ArrayList<Integer> dfs(ArrayList<ArrayList<Integer>> G, boolean[] G_mark, int node, ArrayList<Integer> list){
  50.     G_mark[node] = true;
  51.     if(!list.contains(node)){
  52.       list.add(node);
  53.     }
  54.     for(int next: G.get(node)){
  55.       if(!G_mark[next]){
  56.           list.addAll(dfs(G,G_mark,next,new ArrayList<Integer>()));
  57.       }
  58.     }
  59.    
  60.     return list;
  61.   }
  62.  
  63.   public static void BFS(int x,ArrayList<ArrayList<Integer>> G, boolean[] G_mark, ArrayList<Integer> list){
  64.     LinkedList<Integer> queue = new LinkedList<Integer>();
  65.     G_mark[x] = true;
  66.     queue.add(x);
  67.     while(queue.size()!=0){
  68.       x = queue.poll();
  69.       list.add(x);
  70.       for(int next: G.get(x)){
  71.         if(!G_mark[next]){
  72.           G_mark[next] = true;
  73.           queue.add(next);
  74.         }
  75.       }
  76.     }
  77.   }
  78.  
  79.  
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement