SHARE
TWEET

Untitled

ogv Nov 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Runtime: 2 ms
  2. // Your runtime beats 30.41 % of java submissions.
  3. class Solution {
  4.     public int[] findRedundantDirectedConnection(int[][] edges) {
  5.         int n = edges.length;
  6.        
  7.         int[] in = new int[n+1];
  8.         Arrays.fill(in, -1);
  9.        
  10.         List<Integer>[] adj = new List[n+1];
  11.         for (int node = 1; node <= n; node++) adj[node] = new LinkedList<Integer>();
  12.         for (int edgeNo = 0; edgeNo < n; edgeNo++) adj[edges[edgeNo][0]].add(edgeNo);
  13.        
  14.         int[] drains = null;
  15.         for (int edgeNo = 0; edgeNo < n; edgeNo++) {
  16.             int to = edges[edgeNo][1];
  17.             if (in[to] != -1) {
  18.                 drains = new int[] { in[to], edgeNo };
  19.             }
  20.             in[to] = edgeNo;
  21.         }
  22.        
  23.         if (drains != null) {
  24.             int source = -1;
  25.             for (int node = 1; node <= n; node++){
  26.                 if (in[node] == -1){
  27.                     source = node;
  28.                     break;
  29.                 }
  30.             }
  31.            
  32.             int first = Math.min(drains[0], drains[1]);
  33.             int last = Math.max(drains[0], drains[1]);
  34.            
  35.             if (reachable(source, edges[last][1], last, adj, edges))
  36.                 return edges[last];
  37.             else return edges[first];
  38.         }
  39.    
  40.         boolean[] visited = new boolean[n+1];        
  41.         for (int node = 1; node <= n; node++)
  42.             if (!visited[node]) {
  43.                 int res = dfs(node, visited, adj, edges);
  44.                 if (res != -1) return edges[res];
  45.             }
  46.         return null;
  47.     }
  48.    
  49.     private int dfs(int node, boolean[] visited, List<Integer>[] adj, int[][] edges) {
  50.         visited[node] = true;
  51.        
  52.         for (int edgeNo: adj[node]) {
  53.             int[] edge = edges[edgeNo];
  54.             int next = edge[1];
  55.            
  56.             if (visited[next]) return edgeNo;
  57.            
  58.             int res = dfs(next, visited, adj, edges);
  59.             if (res != -1) return Math.max(res, edgeNo);
  60.         }
  61.        
  62.         return -1;
  63.     }
  64.    
  65.     private boolean reachable(int node, int target, int exclEdge, List<Integer>[] adj, int[][] edges) {
  66.         if (node == target) return true;
  67.        
  68.         for (int edgeNo: adj[node]) {
  69.             if (edgeNo == exclEdge) continue;
  70.             int[] edge = edges[edgeNo];            
  71.             int next = edge[1];
  72.            
  73.             if (reachable(next, target, exclEdge, adj, edges)) return true;
  74.         }
  75.        
  76.         return false;
  77.     }
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top