[JAVA] Union Find Solution(TLE), My Initial Approach
The idea is kind of brute force but it\'s my initial approach to this problem. Basically, for each connection in our connections list, we check whether leaving 
The idea is kind of brute force but it\'s my initial approach to this problem. Basically, for each connection in our connections list, we check whether leaving out of this connection for the UF class, we will have uf.size > 1 which means this connection is a critical connection. As I said, it is brute force and cannot pass all of the test cases but just provide a possible approach that you can present during an interview.\n```\nclass UF {\n\tint[] id, weight;\n\tint size;\n\tpublic UF(int n) {\n\t\tid = new int[n];\n\t\tweight = new int[n];\n\t\tsize = n;\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tid[i] = i;\n\t\t\tweight[i] = 1;\n\t\t}\n\t}\n\tpublic int find(int p) {\n\t\twhile (id[p] != id[id[p]]) {\n\t\t\tid[p] = id[id[p]];\n\t\t\tp = id[p];\n\t\t}\n\t\treturn id[p];\n\t}\n\tpublic void union(int p, int q) {\n\t\tint pp = find(p);\n\t\tint pq = find(q);\n\t\tif (weight[pp] < weight[pq]) {\n\t\t\tid[p] = pq;\n\t\t\tweight[pq] += weight[pp];\n\t\t}\n\t\telse {\n\t\t\tid[q] = pp;\n\t\t\tweight[pp] += weight[pq];\n\t\t}\n\t\tsize--;\n\t}\n}\npublic List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n\tList<List<Integer>> res = new ArrayList<>();\n\tfor (int i = 0; i < connections.size(); i++) {\n\t\tif (!isConnected(connections, n, i)) {\n\t\t\tint from = connections.get(i).get(0);\n\t\t\tint to = connections.get(i).get(1);\n\t\t\tres.add(new ArrayList(Arrays.asList(from, to)));\n\t\t}\n\t}\n\treturn res;\n\n}\npublic boolean isConnected(List<List<Integer>> connections, int n, int cut) {\n\tUF uf = new UF(n);\n\tfor (int i = 0; i < connections.size(); i++) {\n\t\tif (i == cut) continue;\n\t\tList<Integer> connection = connections.get(i);\n\t\tint from = connection.get(0);\n\t\tint to = connection.get(1);\n\t\tint pFrom = uf.find(from);\n\t\tint pTo = uf.find(to);\n\t\tif (pFrom != pTo) {\n\t\t\tuf.union(pFrom, pTo);\n\t\t}\n\t}\n\treturn uf.size == 1;\n}\n```
[]