Leetcode-problems/problem1466.java at main · tejatayi/Leetcode-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//1466. Reorder Routes to Make All Paths Lead to the City Zero

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class problem1466 {

    public static int minReorder(int n, int[][] connections) {

       HashMap<Integer,List<Integer>> org = new HashMap<>();
       HashMap<Integer,List<Integer>> rev = new HashMap<>();

       for(int i=0;i<connections.length;i++)
       {
        int x = connections[i][0];
        int y = connections[i][1];

        if(!org.containsKey(x))
        {
            org.put(x, new ArrayList<>());
        }
        org.get(x).add(y);


        if(!rev.containsKey(y))
        {
            rev.put(y, new ArrayList<>());
        }
        rev.get(y).add(x);

       }

       Queue <Integer> q = new LinkedList<>();
       Set<Integer> set = new HashSet<>();
       q.add(0);
       set.add(0);
       int ans=0;
       while (!q.isEmpty()) {

        int tem=q.poll();


        if(org.containsKey(tem))
        {
            List<Integer> ls = org.get(tem);
            for(int i : ls)
            {
                if(!set.contains(i))
                {
                    q.add(i);
                    set.add(i);
                    ans++;
                }

            }
        }

        if(rev.containsKey(tem))
        {
            List<Integer> ls = rev.get(tem);
            for(int i : ls)
            {
                if(!set.contains(i))
                {
                    q.add(i);
                    set.add(i);
                }

            }
        }
       }


       return ans ;

    }
    public static void main(String[] args) {
        int [][] a = {{1,0},{1,2},{3,2},{3,4}};

        System.out.println(minReorder(5, a));
    }
}