Graph time complexities

user_11211480 0
Viewed 62

Recently I participated in google's coding exam and there are questions on Graph data structures, One of the question is that, they gives an undirected graph G with N nodes and M edges, He gives Q queries where in each query, he gives X Y W, where we have to check whether there is a path from X to Y with every edge must at most contain the weight <= W. So I tried storing the edges in adjacency list representation of graph and used the DFS method and visited array to check whether there is path following given constraints. It solved for partial test cases and not for private one's. So, I though it may be dense graph and I used Matrix representation of graph, it is showing memory limit exceeded. What should I do to solve these kind of problems?

Whenever I use matrix representation it gives memory limit exceeded and if I use Adjacency list representation, it gives time limit exceeded.Question Image

By the way, exam was completed few day back.

This is my first question. If I made any mistake please comment below

graph-algorithm graph data-structures algorithm
1 Answers

This can be solves in O(n log n + q log q), while your DFS solution was O(m*q) and adj matrix solution was O(n^2) space

To solve this problem fast you need to know as DSU (Disjiont Set Union) data structure (also known as Union Find). It supports efficient O(log n) Union of some nodes and can tell if some nodes are connected or not also in O(log n)

  1. Sort all given edges by weight, ascending
  2. sort all given queries by weight, ascending (also save query index, because outputting will need to be in order)
  3. Now process queries one by one, if query asks for path with edges <= w add all still un-added edges to the graph which fit the criteria (using DSU)
  4. Now query can be answered by checking if start end nodes of the query are connected or not (using DSU)

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int Find(int u, vector<int>&P)
{
    return P[u] < 0 ? u : P[u] = Find(P[u],P);
}

void Union(int u, int v, vector<int>&P)
{
    u=Find(u,P);
    v=Find(v,P);
    if(u==v)return;
    P[u]=v;
}

int main()
{
    //input is quite large so we might need fast I/O
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 

    int t,n,m,q;
    cin>>t;

    while(t--)
    {
        cin>>n>>m>>q;
        vector<int>P(n+1,-1),answers(q);
        vector<array<int,3>>edges; //<storing edges as [w, u, v]
        vector<array<int,4>>queries; //<storing queries as [W, x, y, queryId]

        for(int i=0; i<m; i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            edges.push_back({w,u,v});
        }

        for(int i=0; i<q; i++)
        {
            int x,y,W;
            cin>>x>>y>>W;
            queries.push_back({W,x,y,i});
        }

        sort(edges.begin(),edges.end());
        sort(queries.begin(),queries.end());

        int edgeId = 0;

        for(auto&query : queries){
            while(edgeId < edges.size() && edges[edgeId][0] <= query[0]){
                Union(edges[edgeId][1], edges[edgeId][2], P);
                edgeId++;
            }
            answers[query[3]] = Find(query[1],P) == Find(query[2], P);
        }

        for(int i=0; i<q; i++)
            cout<<answers[i]<<(i+1==q?"\n":" ");
    }

}
user_40591450
Related