Complexidades do tempo do gráfico

Question

Recentemente participei do exame de codificação do google e há perguntas sobre estruturas de dados Graph, uma das perguntas é que, eles dão um grafo não direcionado G com N nós e M arestas, Ele dá Q consultas onde em cada consulta, ele dá XYW, onde temos que verificar se existe um caminho de X para Y com cada aresta deve conter no máximo o peso <= W. Então tentei armazenar as arestas na representação da lista de adjacências do grafo e usei o método DFS e visitei o array para verificar se havia é o caminho seguindo as restrições dadas. Resolveu para casos de teste parciais e não para casos particulares. Então, embora possa ser um gráfico denso e usei a representação Matrix do gráfico, ele está mostrando o limite de memória excedido. O que devo fazer para resolver este tipo de problemas?

Sempre que eu uso representação de matriz dá limite de memória excedido e se eu uso representação de lista de adjacência, dá limite de tempo excedido. Imagem da pergunta

A propósito, o exame foi concluído alguns dias atrás.

Esta é a minha primeira pergunta. Se eu cometi algum erro por favor comente abaixo

Answer 1

Isso pode ser resolvido em O(n log n + q log q), enquanto sua solução DFS era O(m*q)e a solução de matriz adj era O(n^2)espaço

Para resolver esse problema rapidamente, você precisa conhecer a estrutura de dados DSU (Disjiont Set Union) (também conhecida como Union Find). Ele suporta União eficiente O(log n)de alguns nós e pode dizer se alguns nós estão conectados ou não também emO(log n)

1. Ordenar todas as arestas por peso, ascendente
2. classifique todas as consultas fornecidas por peso, crescente (também salve o índice de consulta, porque a saída precisará estar em ordem)
3. Agora processe as consultas uma a uma, se a consulta solicitar um caminho com arestas, <= wadicione todas as arestas ainda não adicionadas ao gráfico que atendem aos critérios (usando DSU)
4. Agora a consulta pode ser respondida verificando se start endos nós da consulta estão conectados ou não (usando DSU)

Código de exemplo (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":" ");
    }

}