Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.0 kB
7
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

// Implement Solution Here
bool dfs(int u, int v, vector<bool> &vis, vector<vector<int>> &adj)
{
    // mark vis[u] true since we visited it
    vis[u] = 1;

    for(int nbr : adj[u])
    {
        // if neighbour is v then we can visit v
        if(nbr == v)
        {
            return true;
        }
        // if neighbour is not visited then do a dfs from here
        if(!vis[nbr])
        {
            // if that dfs returns true then we must have reach v.
            if(dfs(nbr, v, vis, adj))
                return true;
        }
    }

    return false;
}
bool RouteBetweenNodes(int u,int v,int n, vector<vector<int> > edges)
{
    // 1d boolean array visited where vis[i] = true means visited
    vector<bool> vis(n);
    // adjacency list
    vector<vector<int>> adj(n);

    // adding all the edges
    for(auto i : edges)
    {
        adj[i[0]-1].push_back(i[1]-1);
    }

    // if we can reach v from u then return true;
    if(dfs(u-1, v-1, vis, adj))
        return 1;

    return 0;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int numberofnodes,edges;
        cin>>numberofnodes>>edges;
        int vertex1,vertex2;
        vector<vector<int > > edgelist;
        for(int i=0;i<edges;i++)
        {
            cin>>vertex1>>vertex2;
            vector<int > temp = {vertex1,vertex2};
            edgelist.push_back(temp);
        }
        int start,end;
        cin>>start>>end;
        bool result = RouteBetweenNodes(start,end,numberofnodes,edgelist);
        cout<<((result)?"yes":"no")<<"\n";
    }
    return 0;
}

/* 
Crio Methodology

Milestone 1: Understand the problem clearly
1. Ask questions & clarify the problem statement clearly.
2. Take an example or two to confirm your understanding of the input/output & extend it to test cases
Milestone 2: Finalize approach & execution plan
1. Understand what type of problem you are solving.
     a. Obvious logic, tests ability to convert logic to code
     b. Figuring out logic
     c. Knowledge of specific domain or concepts
     d. Knowledge of specific algorithm
     e. Mapping real world into abstract concepts/data structures
2. Brainstorm multiple ways to solve the problem and pick one
3. Get to a point where you can explain your approach to a 10 year old
4. Take a stab at the high-level logic & write it down.
5. Try to offload processing to functions & keeping your main code small.
Milestone 3: Code by expanding your pseudocode
1. Make sure you name the variables, functions clearly.
2. Avoid constants in your code unless necessary; go for generic functions, you can use examples for your thinking though.
3. Use libraries as much as possible
Milestone 4: Prove to the interviewer that your code works with unit tests
1. Make sure you check boundary conditions
2. Time & storage complexity
3. Suggest optimizations if applicable
*/