Discover the Nation with none outgoing path from given Graph


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given a 2D array arr[][], the place arr[i] = [Ai, Bi] means there exists a direct path going from nation Ai to nation Bi, the duty is to discover a nation with out an outgoing path.

Be aware: It’s assured that there can be just one such nation and the given graph doesn’t comprise any cycle.


Enter: arr = {{“Germany”, ” Japan”}, {“United States”, “India”}, {“Japan”, “United States”}}
Output: “India” 
Rationalization: Ranging from “Germany” you’ll attain the vacation spot nation “India”. Journey consists of: “Germany” -> “Japan”  -> “United States”  -> “India”.

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

An method utilizing Hashing:

The thought is to map each route A -> B. This can maintain a bit of knowledge that from A we will attain to B. Now Iterate over all nation B, and examine if there exists any route from B to every other nation. If not then that is th required reply.

Comply with the steps under to implement the above thought:

  • Initialize a map for mapping all nation routes.
  • Iterate over the given array arr[][].
    • Map all nation routes A->B into the map.
  • Initialize a variable end result, which can retailer the specified nation.
  • Iterate over the given array arr[][]
    • Verify if there exists any outgoing route to a different nation.
      • If not, then save this as the specified nation.
  • Return the end result.

Beneath is the implementation of the above method.



#embody <bits/stdc++.h>

utilizing namespace std;


string destCountry(vector<vector<string> >& arr)




    unordered_map<string, string> unmap;



    for (auto s : arr)

        unmap[s[0]] = s[1];




    string end result = "";



    for (auto s : arr) {






        if ([1]) == unmap.finish()) {

            end result = s[1];






    return end result;



int predominant()


    vector<vector<string> > arr

        = { { "Germany", "Japan" },

            { "United States", "India" },

            { "Japan", "United States" } };



    cout << destCountry(arr);


    return 0;


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


Leave a Reply