Horje
Find the Country without any outgoing path from given Graph

Given a 2D array arr[][], where arr[i] = [Ai, Bi] means there exists a direct path going from country Ai to country Bi, the task is to find a country without an outgoing path.

Note: It is guaranteed that there will be only one such country and the given graph does not contain any cycle.

Examples:

Input: arr = {{“Germany”, ” Japan”}, {“United States”, “India”}, {“Japan”, “United States”}}
Output: “India” 
Explanation: Starting from “Germany” you will reach the destination country “India”. Trip consists of: “Germany” -> “Japan”  -> “United States”  -> “India”.

Input: arr= [[“B”, “C”], [“D”, “B”], [“C”, “A”]]
Output: “A”

An approach using Hashing:

The idea is to map every route A -> B. This will keep a piece of information that from A we can reach to B. Now Iterate over all country B, and check if there exists any route from B to any other country. If not then this is the required answer.

Follow the steps below to implement the above idea:

  • Initialize a map for mapping all country routes.
  • Iterate over the given array arr[][].
    • Map all country routes A->B into the map.
  • Initialize a variable result, which will store the desired country.
  • Iterate over the given array arr[][]
    • Check if there exists any outgoing route to another country.
      • If not, then save this as the desired country.
  • Return the result.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the country without outgoing path
string destCountry(vector<vector<string> >& arr)
{
    // Initialize a map for mapping all
    // country routes
    unordered_map<string, string> unmap;
 
    // Map all country routes A -> B
    for (auto s : arr)
        unmap[s[0]] = s[1];
 
    // Initialize a variable result, which
    // will store the destination country
    string result = "";
 
    // Iterate over the arr
    for (auto s : arr) {
 
        // Check if there exist any
        // outgoing route to other country
        // If not, then save this as a
        // destination country.
        if (unmap.find(s[1]) == unmap.end()) {
            result = s[1];
            break;
        }
    }
 
    // Return the result
    return result;
}
 
// Driver code
int main()
{
    vector<vector<string> > arr
        = { { "Germany", "Japan" },
            { "United States", "India" },
            { "Japan", "United States" } };
 
    // Function Call
    cout << destCountry(arr);
 
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to find the country without outgoing path
  static String destCountry(String[][] arr)
  {
    // Initialize a map for mapping all
    // country routes
    HashMap<String, String> unmap = new HashMap<>();
 
    // Map all country routes A -> B
    for (var s : arr) {
      unmap.put(s[0], s[1]);
    }
 
    // Initialize a variable result, which
    // will store the destination country
    String result = "";
 
    // Iterate over the arr
    for (var s : arr) {
      // Check if there exist any
      // outgoing route to other country
      // If not, then save this as a
      // destination country.
      if (!unmap.containsKey(s[1])) {
        result = s[1];
        break;
      }
    }
 
    // Return the result
    return result;
  }
 
  public static void main(String[] args)
  {
    String[][] arr = { { "Germany", "Japan" },
                      { "United States", "India" },
                      { "Japan", "United States" } };
    // Function call
    System.out.print(destCountry(arr));
  }
}
 
// This code is contributed by lokeshmvs21.

Python3

# Python code to implement the approach
 
# Function to find the country without outgoing path
def destCountry(arr):
    # Initialize a map for mapping all
    # country routes
    unmap=dict()
     
    # Map all country routes A -> B
    for s in arr:
        unmap[s[0]]=s[1]
     
    # Initialize a variable result, which
    # will store the destination country
    result=""
     
    # Iterate over the arr
    for s in arr:
        # Check if there exist any
        # outgoing route to other country
        # If not, then save this as a
        # destination country.
        if s[1] not in unmap:
            result=s[1]
            break
     
    # Return the result
    return result
     
# Driver code
arr=[["Germany", "Japan"],["United States", "India"],["Japan", "United States"]]
 
# Function Call
print(destCountry(arr))
 
# This code is contributed by Pushpesh Raj.

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
    // Function to find the country without outgoing path
    static string destCountry(string[, ] arr)
    {
        // Initialize a map for mapping all
        // country routes
        Dictionary<string, string> unmap
            = new Dictionary<string, string>();
 
        // Map all country routes A -> B
        for (int i = 0; i < arr.GetLength(0); i++) {
            unmap.Add(arr[i, 0], arr[i, 1]);
        }
 
        // Initialize a variable result, which
        // will store the destination country
        string result = "";
 
        // Iterate over the arr
        for (int i = 0; i < arr.GetLength(0); i++) {
            // Check if there exist any
            // outgoing route to other country
            // If not, then save this as a
            // destination country.
            if (!unmap.ContainsKey(arr[i, 1])) {
                result = arr[i, 1];
                break;
            }
        }
 
        // Return the result
        return result;
    }
 
    // Driver Code
    static public void Main()
    {
        string[, ] arr = { { "Germany", "Japan" },
                           { "United States", "India" },
                           { "Japan", "United States" } };
        // Function call
        Console.WriteLine(destCountry(arr));
    }
}
 
// This code is contributed by Rohit Pradhan

Javascript

   // JavaScript code for the above approach
 
   // Function to find the country without outgoing path
   function destCountry(arr) {
     // Initialize a map for mapping all
     // country routes
     let unmap = new Map();
 
     // Map all country routes A -> B
     for (let s of arr)
       unmap.set(s[0], s[1]);
 
     // Initialize a variable result, which
     // will store the destination country
     let result = "";
 
     // Iterate over the arr
     for (let s of arr) {
 
       // Check if there exist any
       // outgoing route to other country
       // If not, then save this as a
       // destination country.
       if (!unmap.has(s[1])) {
         result = s[1];
         break;
       }
     }
 
     // Return the result
     return result;
   }
 
   // Driver code
   let arr
     = [["Germany", "Japan"],
     ["United States", "India"],
     ["Japan", "United States"]];
 
   // Function Call
   console.log(destCountry(arr));
 
// This code is contributed by Potta Lokesh

Output

India

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
How to iterate over boost graph to get incoming and outgoing edges of vertex? How to iterate over boost graph to get incoming and outgoing edges of vertex?
Delete Maximum edges such that Graph is traversable Delete Maximum edges such that Graph is traversable
Check if all nodes of Undirected Graph can be visited from given Node Check if all nodes of Undirected Graph can be visited from given Node
Minimize rope length to connect given points in a 3D plane Minimize rope length to connect given points in a 3D plane
Edge Relaxation Property for Dijkstra’s Algorithm and Bellman Ford&#039;s Algorithm Edge Relaxation Property for Dijkstra’s Algorithm and Bellman Ford&#039;s Algorithm

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje