We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Kingdom Connectivity
  5. Discussions

Kingdom Connectivity

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 28 Discussions, By:

votes

Please Login in order to post a comment

  • ayushr2
    4 years ago+ 2 comments

    This was a very interesting problem. Took me a while to do this. The solution is pretty simple though. Here are the tricks:

    1. There will be infinite number of paths only if one valid path from 1 to n touches a cycle. So do exactly that. Maintain two sets for path and cycle. As and when you detect a new path, add all those nodes to the set and when you detect a cycle add all cycle nodes to the set. After everything is over, see if these two sets intersect at all. if they do then there are infinite paths.
    2. Since the answer should be mod 10^9, we can infer that there will be large answers. So we use a simple DP trick here. Maintain an array which holds an int for each node. that int represents the number of paths from that node till nth node. When we find a new path, increment this value for all nodes on that path. and MOST importantly, whenever we touch a new node during dfs for which the array value is greater than 0, we know we have explored all possible paths from that node to nth node so we grab its value and increment all nodes on current path with that value and not recurse in that direction.
    3. when we exit the dfs recursion for any node and we see that we did not find any paths to nth node from this node, we set the DP array value for this node to -1. so next time we touch this node, we can see the -1 and not recurse in this direction cuz we wont find anything.

    These tricks are enough to get you through! Here is a very efficient implementation of the above in C++. Feel free to suggest anything! Happy coding!

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <queue>
    #include <algorithm>
    #include <set>
    #include <stack>
    
    #define pb push_back
    #define range(i, x, y) for(int i = x; i < y; i++)
    
    using namespace std;
    
    typedef vector<int> v;
    typedef vector<v> vv;
    
    vv graph;
    v visited;
    int n, m;
    set<int> cycle_nodes;
    set<int> path_nodes;
    v cur_path;
    v memo;
    int MOD = 1000000000;
    
    void read_graph();
    
    void dfs(int node);
    
    void update_path_nodes(int inc);
    
    void update_cycle_nodes(int cycle_start);
    
    bool found_infinite_solution();
    
    int main() {
        read_graph();
        dfs(0);
        if (found_infinite_solution())
            cout << "INFINITE PATHS";
        else
            cout << memo[0];
        return 0;
    }
    
    bool found_infinite_solution() {
        for(int cycle_node : cycle_nodes) {
            if (path_nodes.find(cycle_node) != path_nodes.end())
                return true;
        }
    
        return false;
    }
    
    void dfs(int node) {
        visited[node] = true;
        cur_path.pb(node);
    
        if (node == n - 1)
            update_path_nodes(1);
        else {
            for (int next : graph[node]) {
                if (visited[next])
                    update_cycle_nodes(next);
                else {
                    if (memo[next] > 0)
                        update_path_nodes(memo[next]);
                    if (memo[next] == 0)
                        dfs(next);
                }
            }
        }
    
        if (memo[node] == 0)
            memo[node] = -1;
    
        visited[node] = false;
        cur_path.pop_back();
    }
    
    void update_cycle_nodes(int cycle_start) {
        auto rit = cur_path.rbegin();
        for(; *rit != cycle_start; rit++) {
            cycle_nodes.insert(*rit);
        }
        cycle_nodes.insert(cycle_start);
    }
    
    void update_path_nodes(int inc) {
        for (int cur : cur_path) {
            path_nodes.insert(cur);
            memo[cur] += inc;
            memo[cur] %= MOD;
        }
    }
    
    void read_graph() {
        cin >> n >> m;
        range(i, 0, n) {
            graph.pb(v());
            visited.pb(false);
            memo.pb(0);
        }
    
        int x, y;
        range(i, 0, m) {
            cin >> x >> y;
            graph[--x].pb(--y);
        }
    }
    
    9|
    Permalink
  • stevelang
    6 years ago+ 1 comment

    Must the path terminate as soon as we've reached the warfare city? Or can we travel through the warfare city, if it is on a loop?

    For example

    4 4
    1 2
    2 3
    3 4
    4 2
    

    Where there is a direct path 1->2->3->4, but also 1->2->3->4->2->3->4...

    6|
    Permalink
  • aayush_break
    6 years ago+ 1 comment

    i'm having this doubt ...

    once the person enters the loop then he cannot escape out since it is a directed graph and hence "Infinite paths",

    but if he is able to choose a path other than the "looped path" and reaches the destination, then we are supposed to count that path as valid....

    so according to the question is this what i have to do?

    please help!!

    for eg : consider the path

        1->2
        1->3
        2->3
        4->2
        3->4
        4->5
    

    in this 2->3->4->2 forms a loop path

    but 1->3->4->5 can lead to the destination

    4|
    Permalink
  • venkatesh_010
    6 years ago+ 1 comment

    I am not getting a correct answer for test case 3 and test case 9 they have a value in their o/p though their is a cycle in the graph.

    2|
    Permalink
  • gauravyadav121
    9 years ago+ 4 comments

    For test case 20 33 10 15 15 17 8 18 12 5 11 4 16 14 10 17 12 5 4 12 10 15 1 7 2 20 1 10 2 20 12 5 15 9 8 11 16 6 4 12 13 2 15 17 3 15 14 8 11 19 1 16 9 20 9 13 16 18 14 6 1 3 12 5 4 16 6 8 For this test case Output is 9 but here exists a path with cycle i.e 1->16->6->8->11->4->16... here 16 is visited again Correct me if I am wrong!!

    2|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature