Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.LinkedList;
- // ADDITIONAL IMPORTS ARE NOT ALLOWED
- class Main {
- public static void main(String[] args) {
- // Uncomment the following two lines if you want to read from a file
- In.open("public/small.in");
- Out.compareTo("public/small.out");
- int n = In.readInt(); //number of vertices
- int edges = In.readInt();
- int x = In.readInt();
- int y = In.readInt();
- ArrayList<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>(n);
- ArrayList<ArrayList<Integer>> G_r = new ArrayList<ArrayList<Integer>>(n);
- for (int i = 0; i < n; i++) {
- G.add(new ArrayList<Integer>());
- G_r.add(new ArrayList<Integer>());
- }
- for (int i = 0; i < edges; i++) {
- int src = In.readInt();
- int trg = In.readInt();
- G.get(src).add(trg);
- G_r.get(trg).add(src);
- }
- Out.println(countInBetween(n, G,G_r, x, y));
- // Uncomment this line if you want to read from a file
- In.close();
- }
- public static int countInBetween(int n, ArrayList<ArrayList<Integer>> G,ArrayList<ArrayList<Integer>> G_r, int x, int y) {
- boolean[] G_mark = new boolean[n];
- boolean[] G_mark_r = new boolean[n];
- ArrayList<Integer> list_forward = new ArrayList<Integer>();
- ArrayList<Integer> list_backward = new ArrayList<Integer>();
- BFS(x,G,G_mark,list_forward);
- BFS(y,G_r,G_mark_r,list_backward);
- list_forward.retainAll(list_backward);
- return list_forward.size();
- }
- public static ArrayList<Integer> dfs(ArrayList<ArrayList<Integer>> G, boolean[] G_mark, int node, ArrayList<Integer> list){
- G_mark[node] = true;
- if(!list.contains(node)){
- list.add(node);
- }
- for(int next: G.get(node)){
- if(!G_mark[next]){
- list.addAll(dfs(G,G_mark,next,new ArrayList<Integer>()));
- }
- }
- return list;
- }
- public static void BFS(int x,ArrayList<ArrayList<Integer>> G, boolean[] G_mark, ArrayList<Integer> list){
- LinkedList<Integer> queue = new LinkedList<Integer>();
- G_mark[x] = true;
- queue.add(x);
- while(queue.size()!=0){
- x = queue.poll();
- list.add(x);
- for(int next: G.get(x)){
- if(!G_mark[next]){
- G_mark[next] = true;
- queue.add(next);
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement