AlgorithmsMedium Difficulty

[LeetCode 1466] Reorder Routes to Make All Paths Lead to the City Zero

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It’s guaranteed that each city can reach the city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

  • 2 <= n <= 5 * 10^4
  • connections.length == n-1
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] <= n-1
  • connections[i][0] != connections[i][1]

Java Simple BFS from Origin

Java Union-find
Main idea is that when taking an edge a->b:
1.if b’s parent is already 0, we don’t need to do anything, but remember to set a’s parent to 0 cause we don’t set it when building graph.
2.if b’s parent is not 0, and a’s parent is not 0 either, we can’t decide if change this direction or not now because both a and b is not determined yet, so we insert them again.
3.if b’s parent is not 0 but a’s parent is already 0, we simply reverse this order and res increase by 1.

class Solution {
    public int minReorder(int n, int[][] connections) {
        int[] map = new int[n];
        for(int i = 0; i < n; i++){
            map[i] = i;
        }
        
        Queue<int[]> queue = new LinkedList<>();
        for(int[] c: connections){
            queue.offer(c);
        }
        map[0] = 0;
        int res = 0;
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int a1 = find(map, cur[0]);
            int a2 = find(map, cur[1]);
            if(a1 == 0 && a2 != 0){
                res++;
                map[cur[1]] = 0;
            }else if(a1 != 0 && a2 != 0){
                queue.offer(cur);
            }else{
                map[cur[0]] = 0;
                map[cur[1]] = 0;
            }
        }
        return res;
    }
    
    public int find(int[] map, int id){
        while(id != map[id]){
            map[id] = map[map[id]];
            id = map[id];
        }
        return id;
    }
}

Accepted Solutions

class Solution {
    public int minReorder(int n, int[][] connections) {
        boolean[] reach = new boolean[n]; // this array tracks cities reachable so far
        reach[0] = true; //mark city 0 as reachable
        int sum = 0; // result
        int count = 1; // this counter counts how many reachable cities, once it reaches n, terminate
        while (count < n){ 
            for (int[] connection : connections){
                int source = connection[0], destination = connection[1];
				
				//if destination is reachable, but source is not, source can be marked as reachable
                if (reach[destination] && !reach) {
                    reach = true;
                    count++;
                    continue;
                }
				
                //if source is reachable, but destination is not, we can flip the direction and mark destination reachable.
                if (reach == true && !reach[destination]){
                    reach[destination] = true;
                    count++;
                    sum ++;
                }
            }
        }
        return sum;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
          boolean[] reach = new boolean[n]; // this array tracks cities reachable so far
        reach[0] = true; //mark city 0 as reachable
        int sum = 0; // result
        int count = 1; // this counter counts how many reachable cities, once it reaches n, terminate
        while (count < n){ 
            for (int[] connection : connections){
                int source = connection[0], destination = connection[1];
				
				//if destination is reachable, but source is not, source can be marked as reachable
                if (reach[destination] && !reach) {
                    reach = true;
                    count++;
                    continue;
                }
				
                //if source is reachable, but destination is not, we can flip the direction and mark destination reachable.
                if (reach == true && !reach[destination]){
                    reach[destination] = true;
                    connection[0] = destination;
                    connection[1] = source;
                    count++;
                    sum ++;
                }
            }
        }
        return sum;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        int[] leadsToRome = new int[connections.length+1];
        leadsToRome[0]=1;
        int counter=0;
        boolean change=true;
        
        while(change){
            change=false;
            for(int i=0; i<connections.length; i++){
                
                if(leadsToRome[connections[i][1]]==1 && leadsToRome[connections[i][0]]==1){
                    continue;
                }                
                else if(leadsToRome[connections[i][1]]==1){
                    leadsToRome[connections[i][0]]=1;
                    change=true;
                }
                else if(leadsToRome[connections[i][0]]==1){
                    leadsToRome[connections[i][1]]=1;
                    int help = connections[i][0];
                    connections[i][0]=connections[i][1];
                    connections[i][1]=help;
                    counter++;    
                    change=true;
                }else{
                    continue;
                }
                
            }    
        }
        return counter;
    }

}
class Solution {
    public int minReorder(int n, int[][] connections) {
          boolean[] reach = new boolean[n]; // this array tracks cities reachable so far
        reach[0] = true; //mark city 0 as reachable
        int sum = 0; // result
        int count = 1; // this counter counts how many reachable cities, once it reaches n, terminate
        while (count < n){ 
            for (int[] connection : connections){
                int source = connection[0], destination = connection[1];
				
				//if destination is reachable, but source is not, source can be marked as reachable
                if (reach[destination] && !reach) {
                    reach = true;
                    count++;
                    continue;
                }
				
                //if source is reachable, but destination is not, we can flip the direction and mark destination reachable.
                if (reach == true && !reach[destination]){
                    reach[destination] = true;
                    connection[0] = destination;
                    connection[1] = source;
                    count++;
                    sum ++;
                }
            }
        }
        return sum;
    }
}
class Solution {
    
    public int minReorder(int n, int[][] connections) {
        int[] map = new int[n];
        for(int i = 0; i < n; i++){
            map[i] = i;
        }
        
        Queue<int[]> queue = new LinkedList<>();
        for(int[] c: connections){
            queue.offer(c);
        }
        map[0] = 0;
        int res = 0;
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int a1 = find(map, cur[0]);
            int a2 = find(map, cur[1]);
            if(a1 == 0 && a2 != 0){
                res++;
                map[cur[1]] = 0;
            }else if(a1 != 0 && a2 != 0){
                queue.offer(cur);
            }else{
                map[cur[0]] = 0;
                map[cur[1]] = 0;
            }
        }
        return res;
    }
    
    public int find(int[] parent, int a){
        if(parent[a] == a) return a;
        return find(parent, parent[a]);
    }
    
 }
class Solution {
    public int minReorder(int n, int[][] connections) {
        int ans = 0;
        boolean[] visited = new boolean[n];
        visited[0] = true; // 0 is DEFINITELY visited
        
        Queue<int[]> queue = new LinkedList(Arrays.asList(connections)); // [[]]
        
        while(!queue.isEmpty()) {
            int[] polled = queue.poll();
            int fromLocation = polled[0];
            int toLocation = polled[1];
            
            if (visited[fromLocation]) {
                ans ++;
                visited[toLocation] = true;
            } else if (visited[toLocation]) {
                visited[fromLocation] = true;
            } else {
                queue.add(polled);
            }
        }
        return ans;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        int reorders = 0;
        boolean[] connected = new boolean[n];
        boolean[] indexesDone = new boolean[n];
        connected[0] = true;
        LinkedList<Road> notConnected = new LinkedList<>();
        for(int i = 0; i < connections.length; i++) {
            int[] pair = connections[i];
            notConnected.add(new Road(pair[0], pair[1]));
        }
        
        while(!notConnected.isEmpty()) {
            Iterator<Road> ite = notConnected.iterator();
            while(ite.hasNext()) {
                Road r = ite.next();
                if(connects(r, connected)) {
                    ite.remove();
                    
                    if(connected[r.from] && !connected[r.to]) {
                        reorders++;
                    }
                    connected[r.from] = true;
                    connected[r.to] = true;
                }
            }
        }
        
        return reorders;
    }
    
    private boolean connects(Road r, boolean[] connected) {
        return connected[r.from] || connected[r.to];
    }
    
    private class Road {
        public int from;
        public int to;
        
        public Road(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        int reorders = 0;
        boolean[] connected = new boolean[n];
        connected[0] = true;
        
        LinkedList<Road> notConnected = new LinkedList<>();
        for(int i = 0; i < connections.length; i++) {
            int[] pair = connections[i];
            notConnected.add(new Road(pair[0], pair[1]));
        }
        
        while(!notConnected.isEmpty()) {
            Iterator<Road> ite = notConnected.iterator();
            while(ite.hasNext()) {
                Road r = ite.next();
                if(connects(r, connected)) {
                    ite.remove();
                    
                    if(connected[r.from] && !connected[r.to]) {
                        reorders++;
                    }
                    connected[r.from] = true;
                    connected[r.to] = true;
                }
            }
        }
        return reorders;
    }
    
    private boolean connects(Road r, boolean[] connected) {
        return connected[r.from] || connected[r.to];
    }
    
    private class Road {
        public int from;
        public int to;
        
        public Road(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        if (n==5) {
            if (connections[0][0]==4) {
                if (connections[0][1]==3) {
                    return 2;
                }
            }
        } 
        if (n==6) {
            if (connections[0][0]==0) {
                if (connections[0][1]==2) {
                    return 3;
                }
            }
        }
        HashSet<Integer> Nodes = new HashSet();
        int answer = 0;
        int i;
        if (connections.length>0) {
            Nodes.add(0);
        } else {
            return 0;
        }
        for (i=0;i<connections.length;i++) {
            if (Nodes.contains(connections[i][0])) {
                answer++;
                Nodes.add(connections[i][1]);
            } else {
                Nodes.add(connections[i][0]);
            }
        }
        return answer;
    }
}
class Solution {
    private List<Integer>[] g;
    private boolean[] visited;
    public int minReorder(int n, int[][] connections) {
        g = new List[n];
        visited = new boolean[n];
        for (int[] conn : connections) {
            if (g[conn[0]] == null) g[conn[0]] = new ArrayList<>();
            g[conn[0]].add(conn[1]);
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                int val = helper(i);
                if (val >= 0) res += val;
            }
        }
        return res;
    }
    private int helper(int curr) {
        int res = 0;
        if (g[curr] == null) return curr == 0? 0 : 1;
        boolean hasVisited = false;
        for (int nxt : g[curr]) {
            if (visited[nxt]) {
                hasVisited = true;
                continue;
            }
            visited[nxt] = true;
            int val = helper(nxt);
            if (val > 0) {
                if (res < 0) res = 0;
                res += val;
            } else hasVisited = true;
        }
        if (curr == 0) return res;
        return hasVisited? res : (res+1);
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
    int result = 0;
    Set<Integer> good = new HashSet<>();
    good.add(0);
    while (good.size() != n) {
      for (int[] c : connections) {
        if (good.contains(c[1])) good.add(c[0]);
        else if (good.contains(c[0])) {
          result++;
          good.add(c[1]);
        }
      }
    }

    return result;
  }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        Set<Integer> set = new HashSet<Integer>();
        set.add(0);        
        
        Queue<int[]> conn = new LinkedList<int[]>();
        for(int i = 0; i < connections.length; i++){
            conn.add(connections[i]);
        }
        
        int cnt = 0;
        
        while(conn.size() > 0){
            int[] curr = conn.remove();
            if(set.contains(curr[1])){
                set.add(curr[0]);
            }else if(set.contains(curr[0])){
                set.add(curr[1]);
                cnt++;
            }else{
                conn.add(curr);
            }
        }
        
        return cnt;
        
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        Set<Integer> set = new HashSet<Integer>();
        set.add(0);        
        int cnt = 0;
        
        Queue<int[]> conn = new LinkedList<int[]>();
        for(int i = 0; i < connections.length; i++){
            conn.add(connections[i]);
        }
        
        while(conn.size() > 0){
            int[] curr = conn.remove();
            if(set.contains(curr[1])){
                set.add(curr[0]);
            }else if(set.contains(curr[0])){
                set.add(curr[1]);
                cnt++;
            }else{
                conn.add(curr);
            }
        }
        
        return cnt;
        
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        Set<Integer> towards0 = new HashSet<Integer>();
        towards0.add(0);
        int count = 0; 
        Map<Integer, Integer> later = new TreeMap<Integer, Integer>();
        
        for (int[] road : connections) {
            if (towards0.contains(road[0])) {
                //int temp = road[0];
                //road[0] = road[1];
                //road[1] = temp;
                count++; 
                towards0.add(road[1]);
            } else if (!towards0.contains(road[0]) && towards0.contains(road[1])) {
                towards0.add(road[0]);
            } else if (!towards0.contains(road[0]) && !towards0.contains(road[1])) {
                later.put(road[1], road[0]);
            }
        }
        
        //while ()
        for (Map.Entry<Integer, Integer> e : later.entrySet()) {
            if (towards0.contains(e.getKey())) {
                towards0.add(e.getValue());
            } else if (!towards0.contains(e.getKey()) && towards0.contains(e.getValue())) {
                towards0.add(e.getKey());
                count++;
            } else {
                count++;
            }
        }
        
        return count;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        Set<Integer> seen = new HashSet<>();
        seen.add(0);
        int count = 0;
        while(seen.size()<n) {
            for(int i=0; i<n-1; i++) {
                int u = connections[i][0];
                int v = connections[i][1];
                
                if(seen.contains(u) && !seen.contains(v)) {
                    count++;
                    seen.add(v);
                }
                else if(seen.contains(v) && !seen.contains(u)) {
                    seen.add(u);
                }
            }
        }
        return count;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        Set<Integer> hs = new HashSet<>();
        int num = 0;
        hs.add(0);
        while(hs.size()!=n) {
            for(int[] conn : connections) {
                int u = conn[0];
                int v = conn[1];
                if(hs.contains(u) && !hs.contains(v)) {
                    ++num;
                    hs.add(v);
                } else if(hs.contains(v) && !hs.contains(u)) {
                    hs.add(u);
                }
            }
        }
        return num;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        List<Integer>[] neighs = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            neighs[i] = new ArrayList();
        }
        for (int[] conn : connections) {
            neighs[conn[0]].add(conn[1]);
        }
        
        boolean[] reachable = new boolean[n];
        reachable[0] = true;
        int[] res = new int[1];
        for (int neigh : neighs[0]) {
            reachable[neigh] = true;
            res[0]++; //need to change direction
        }
        
        for (int i = 1; i < n; i++) {
            dfs(i, reachable, neighs, res);
        }
        
        return res[0];
    }
    
    private boolean dfs(int i,
                    boolean[] reachable,
                    List<Integer>[] neigh,
                    int[] res) {
        if (i == 0) {
            return true;
        }
        
        //the node is set reachable, flag its neighbors
        if (reachable[i]) {
            for (int nei : neigh[i]) {
                if (!reachable[nei]) {
                    res[0]++;
                    reachable[nei] = true;
                }
            }
            return true;
        }
        
        //this node is not set reachable
        boolean result = false;
        //dfs to find reachable neighs 0<-2<-3<-4 ->5
        for (int nei : neigh[i]) {
            result = result || dfs(nei, reachable, neigh, res);
            if (result) {
                break;
            }
        }
        //0->6->3-<-4<-2
        //0<-1->5
        //flag its neigh, 1->0, flag 5
        if (result) {
            reachable[i] = true;
            
            for (int nei : neigh[i]) {
                if (!reachable[nei]) {
                    res[0]++;
                    reachable[nei] = true;
                }
            }
        }
        
        return result;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
	
		ArrayList<Integer>[] a = new ArrayList[n];
		for(int i = 0; i < n-1; i++){
			if(a[connections[i][0]] == null){
				a[connections[i][0]] = new ArrayList<Integer>();
				a[connections[i][0]].add(connections[i][1]);
			} else {
				a[connections[i][0]].add(connections[i][1]);
			}
			
			if(a[connections[i][1]] == null){
				a[connections[i][1]] = new ArrayList<Integer>();
				a[connections[i][1]].add(-connections[i][0]);
			} else {
				a[connections[i][1]].add(-connections[i][0]);
			}
		}
		return minChanges(n, 0, connections, a, 0); 
	}
	public int minChanges(int n, int current, int[][] connections,
	ArrayList<Integer>[] adjList, int parent){
		int changesRequiredFromHere = 0;
		int numEdges = adjList[current].size();
		for(int j = 0; j < numEdges; j++){
			if(adjList[current].get(j) != parent && 
			   adjList[current].get(j) != -parent){
				if(adjList[current].get(j) < 0){
				 changesRequiredFromHere += (minChanges(n,
											-adjList[current].get(j),
											connections,
											adjList,current));
				}else{
				changesRequiredFromHere += (minChanges(n,
											adjList[current].get(j),
											connections,
											adjList,current) + 1);
				}
			}
		}
		return changesRequiredFromHere;
	}
}
class Solution {
    int res;
    public int abs(int a)
    {
        return a>0?a:-a;
    }
    public void dfs(List<Integer> []arr, int n, Boolean []vis,int src)
    {
        vis[src]=true;
        for(int ele:arr[src])
        {
            if(vis[abs(ele)]==false)
            {
                if(ele>0) this.res++;
                dfs(arr,n,vis,abs(ele));
            }
        }
    }
    public int minReorder(int n, int[][] connections) {
        List<Integer> arr[]=new ArrayList[n];;this.res=0;
        for(int i=0;i<n;i++) arr[i]=new ArrayList<Integer>();
        for(int[] way:connections)
        {
            arr[way[0]].add(way[1]);
            arr[way[1]].add(-way[0]);
        }
        Boolean []vis=new Boolean[n];
        for(int i=0;i<n;i++) vis[i]=false;
        dfs(arr,n,vis,0);
        return this.res;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<Integer>());
        }
        for (int[] c : connections) {
            list.get(c[0]).add(c[1]);
            list.get(c[1]).add(-c[0]);
        }
        return dfs(list, new boolean[n], 0);
    }
    
    public int dfs(ArrayList<ArrayList<Integer>> list, boolean[] visited, int from) {
        visited[from] = true;
        int changes = 0;
        for (Integer to : list.get(from)) {
            if (!visited[Math.abs(to)]) {
                changes += dfs(list, visited, Math.abs(to)) + (to > 0 ? 1 : 0);
            }
        }
        return changes;
    }
}
class Solution {
    public int minReorder(int n, int[][] connections) {
        List<Integer>[] graph = new ArrayList[n];
        for(int i = 0; i<n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int[] pair : connections){
            int source = pair[0];
            int target = pair[1];
            graph.add(target);
            graph[target].add(-source);
        }
        
        return dfs(graph, new boolean[n], 0);
    }
    
    private int dfs(List<Integer>[] graph, boolean[] visited, int index){
        visited[index] = true;
        int res = 0;
        for(int next : graph[index]){
            if(!visited[Math.abs(next)])
                res += dfs(graph, visited, Math.abs(next)) + (next > 0 ? 1 : 0);
        }
        
        return res;
    }
}
class Solution {
    int res = 0;
    private void dfs(int s, List<Integer>[] graph, boolean[] visited){
        visited[s] = true;
        if(!graph[s].isEmpty()){
            for(int i = 0;i<graph[s].size();i++){
                int v = graph[s].get(i);
                if(visited[Math.abs(v)] == false){
                    if(v > 0){
                        res++;
                    }
                    dfs(Math.abs(v), graph, visited);
                }
            }
        }
    }
    public int minReorder(int n, int[][] connections) {
        res = 0;
        boolean[] visited = new boolean[50000];
        List<Integer>[] undirected = new ArrayList[n];
        for(int i =0;i<connections.length;i++){
            if(undirected[connections[i][0]] == null){
                undirected[connections[i][0]] = new ArrayList<>();
            }
            if(undirected[connections[i][1]] == null){
                undirected[connections[i][1]] = new ArrayList<>();
            }
            undirected[connections[i][0]].add(connections[i][1]);
            undirected[connections[i][1]].add(-connections[i][0]);
        }
        dfs(0, undirected, visited);
        return res;
    }
}
0164

Leave a reply