Complexités temporelles du graphique

Question

Récemment, j'ai participé à l'examen de codage de Google et il y a des questions sur les structures de données Graph, l'une des questions est que, ils donnent un graphe non dirigé G avec N nœuds et M arêtes, Il donne des requêtes Q où dans chaque requête, il donne XYW, où nous devons vérifier s'il existe un chemin de X à Y avec chaque arête qui doit au plus contenir le poids <= W.J'ai donc essayé de stocker les arêtes dans la représentation de liste de contiguïté du graphe et utilisé la méthode DFS et le tableau visité pour vérifier s'il y avait est le chemin suivant des contraintes données. Il a résolu pour les cas de test partiels et non pour les cas privés. Donc, je pensais que c'était peut-être un graphique dense et j'ai utilisé une représentation matricielle du graphique, cela montre que la limite de mémoire est dépassée. Que dois-je faire pour résoudre ce genre de problèmes?

Chaque fois que j'utilise une représentation matricielle, cela donne une limite de mémoire dépassée et si j'utilise une représentation de liste d'adjacence, cela donne une limite de temps dépassée. Image de la question

À propos, l'examen a été terminé il y a quelques jours.

C'est ma première question. Si j'ai fait une erreur, veuillez commenter ci-dessous

Answer 1

Cela peut être résolu dans O(n log n + q log q), alors que votre solution DFS était O(m*q)et que la solution de matrice adj était l' O(n^2)espace

Pour résoudre ce problème rapidement, vous devez connaître la structure de données DSU (Disjiont Set Union) (également appelée Union Find). Il prend en charge l' O(log n)Union efficace de certains nœuds et peut dire si certains nœuds sont connectés ou non également dansO(log n)

1. Trier toutes les arêtes données par poids, par ordre croissant
2. trier toutes les requêtes données par poids, par ordre croissant (enregistrez également l'index de la requête, car la sortie devra être dans l'ordre)
3. Maintenant, traitez les requêtes une par une, si la requête demande un chemin avec des arêtes, <= wajoutez toutes les arêtes encore non ajoutées au graphique qui correspondent aux critères (en utilisant DSU)
4. Il est désormais possible de répondre à la requête en vérifiant si les start endnœuds de la requête sont connectés ou non (en utilisant DSU)

Exemple de 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":" ");
    }

}