# Monika
###### tags: `mock_interview`


[1,2,4]
adj[1] = {2,4}
bool dfs(int s, int d, vector<vector<int>>&adj, vector<int>&visit){
    if(s==d)return true;
    visit[s] = 1;
    bool reachable = false;
    for(int i = 0;i<adj[s].size();i++){
        if(!visited[adj[s][i]]){
            reachable = reachable|dfs(adj[s][i],d,adj,visit);
        }
    }
    visit[s] = 0;
    return reachable;
}
bool canReach(vector<vector<int>>&weight, int maxWeight, int source, int destination, int noOfVertex){
    vector<vector<int>>adj(noOfVertex+1);
    
    for(int i = 0;i<weight.size();i++){
        //weight[i][0] , weight[i][1] are the vertex that are connected using weight w that is weight[i][2]
        int v1 = weight[i][0];
        int v2 = weight[i][1];
        int w = weight[i][2];
        
        if(w < maxWeight){
            adj[v1].push_back(v2);
            adj[v2].push_back(v1);
        }
    }
    
    vector<int>visit(noOfVertex+1,0);
    return dfs(source, destination, visit, adj);
    
    // not STL
    vector<bool> vis;
    for(auto v: vis) {
        v = false;
    }
    
    // STL
    vector<int> nums;
    for(auto n: nums) {
        n += 1;
    }
}

[0, 1, 10]

[
    [0, 1, 10],
    [1, 2, 5],
    ...
    [10, 15, 5],
]

[true, false, true, ... ]

//minimum spanning tree

{1,2,5}
{0,2,2}
{0,1,10}

0 -> 2 ->1 
  
query = {source, destination, weight}

vector<bool> IsReachable(vector<vector<int>>&weight, vector<query>&queries, int noOfVertex){
    
    vector<vector<pair<int,int>>>&adj;
    for(int i = 0;i<weight.size();i++){
        //weight[i][0] , weight[i][1] are the vertex that are connected using weight w that is weight[i][2]
        int v1 = weight[i][0];
        int v2 = weight[i][1];
        int w = weight[i][2];
        adj[v1].push_back({v2,w});
        adj[v2].push_back({v1,w});
        
    }
    
    vector<int>parent(noOfVertex+1);
    for(int i=0;i<parent.size();i++)parent[i] = i;
    
    int st = 1;
    priority_queue<pair<int,int>>pq;
    
    for(int i =0;i<adj[st].size();i++){
        pq.push(adj[st][i]);
    }
    int p1 = st;
    while(!pq.empty){
        pair<int,int> top = pq.top();
        pq.pop();
        int p2 = findParent(top.first);
        
        if(p1!=p2){
            parent[p2] = p1;
            for(int i =0;i<adj[top.first].size();i++){
                pq.push(adj[top.first][i]);
             }
        }
              
    }
    
    //query -> O(n) -> parents
    
}

// struct a min spannning
// sort edge
// for each Query