Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- /**
- IDEA:
- Before adding edge (u, v), check if there is already a path from u to v in the graph.
- If a path already exists → adding (u,v) creates a cycle → return that edge.
- Otherwise → add the edge and continue.
- */
- public int[] findRedundantConnection(int[][] edges) {
- int n = edges.length;
- // Step-1 Create an adjacency list
- ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
- for(int i=0; i<=n; i++)
- {
- adj.add(new ArrayList<Integer>());
- }
- // Step-2 Connect edges in adjacency list
- for(int[] edge : edges)
- {
- int u = edge[0];
- int v = edge[1];
- boolean[] visited = new boolean[n+1];
- // Check if path already exists
- if(dfs(adj, visited, u, v))
- {
- return edge;
- }
- // Otherwise add edge
- adj.get(u).add(v);
- adj.get(v).add(u);
- }
- return new int[0];
- }
- public boolean dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, int node, int targetNode)
- {
- if(node == targetNode)
- return true;
- visited[node] = true;
- for(int v : adj.get(node))
- {
- if(!visited[v])
- {
- if(dfs(adj, visited, v, targetNode))
- return true;
- }
- }
- return false;
- }
- }
RAW Paste Data
Copied
