amazon_practice_problems/critical-connections-in-a-network.java at main · KhadijahFlowers/amazon_practice_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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class Solution {

    public class Graph {
        public ArrayList<Node> g;

        public Graph(int n) {
            g = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                g.add(new Node(i));
            }
        }

        public void addEdge(int val1, int val2) {
            g.get(val1).nodes.add(g.get(val2));
            g.get(val2).nodes.add(g.get(val1));
        }

        public boolean dfs(Node n, Stack<Node> s) {
            helper(n, s);
            for (int i = 0; i < g.size(); i++) {
                if (g.get(i).mark) {
                    return false;
                }
            }
            return true;

        }

        public void helper(Node n, Stack<Node> s) {
            for (int i = 0; i < n.nodes.size(); i++) {
                s.push(n.nodes.get(i));
            }

            while (!s.empty()) {
                Node nod = s.pop();
                if (nod.mark) {
                    nod.mark = false;
                    dfs(nod, s);
                }
            }
        }

        public void deleteEdge(int val1, int val2) {

            for (int i = 0; i < g.get(val1).nodes.size(); i++) {
                if (g.get(val1).nodes.get(i).val == val2) {
                    g.get(val1).nodes.remove(i);
                }
            }

            for (int i = 0; i < g.get(val2).nodes.size(); i++) {
                if (g.get(val2).nodes.get(i).val == val1) {
                    g.get(val2).nodes.remove(i);
                }
            }

        }

        public void reset() {
            for (int i = 0; i < g.size(); i++) {
                g.get(i).mark = true;
            }
        }
    }

    public class Node {

        public int val;
        public boolean mark = true;
        public ArrayList<Node> nodes;
        public Node(int n) {
            val = n;
            nodes = new ArrayList<>();

        }

    }

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {

        ArrayList<List<Integer>> arr = new ArrayList<>();

        Graph g = new Graph(n);
        for (int i = 0; i < connections.size(); i++) {

            int one = connections.get(i).get(0);
            int two = connections.get(i).get(1);

            g.addEdge(one, two);
        }

        for (int skip = 0; skip < connections.size(); skip++) {
            int one = connections.get(skip).get(0);
            int two = connections.get(skip).get(1);
            g.deleteEdge(one, two);

            if (!g.dfs(g.g.get(0), new Stack<Node>())) {
                arr.add(connections.get(skip));
            }

            g.addEdge(one, two);
            g.reset();
        }

        return arr;
    }
}