图时间复杂度

Question

最近参加了google的编码考试，有Graph数据结构的题，其中一个问题是，他们给出了一个具有 N 个节点和 M 条边的无向图 G，他给出了 Q 个查询，在每个查询中，他给出了 X Y W，我们必须检查每条边是否存在从 X 到 Y 的路径最多必须包含权重 <= W。所以我尝试将边存储在图的邻接表表示中，并使用 DFS 方法和访问数组来检查是否存在遵循给定约束的路径。它解决了部分测试用例而不是私人测试用例。所以，虽然它可能是密集图并且我使用了图的矩阵表示，但它显示超出了内存限制。我应该怎么做才能解决这类问题？

每当我使用矩阵表示时，它都会超出内存限制，如果我使用邻接表表示，它会超出时间限制。Question Image

顺便说一句，前几天考试结束了。

这是我的第一个问题。如果我有任何错误，请在下面评论

Answer 1

这可以在 O(n log n + q log q) 中解决，而您的 DFS 解决方案是 O(m*q)，adj 矩阵解决方案是 O(n^2) space

要快速解决此问题，您需要了解 DSU（Disjiont Set Union）数据结构（也称为 Union Find）。它支持一些节点的高效 O(log n) 并集，并且可以在 O(log n)

中判断某些节点是否连接

按权重升序对所有给定的边进行排序
按权重升序对所有给定查询进行排序（同时保存查询索引，因为输出需要按顺序排列）
现在，如果查询要求带有边的路径 <= w，则将所有仍然 un-added 的边添加到符合条件的图中（使用 DSU）
现在可以通过检查 start end 个查询节点是否已连接（使用 DSU）来回答查询

示例代码（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":" ");
    }

}

图时间复杂度

Graph time complexities

algorithm

graph

graph-algorithm

data-structures