Đồ thị thời gian phức tạp

Question

Gần đây tôi đã tham gia kỳ thi viết mã của google và có câu hỏi về cấu trúc dữ liệu Biểu đồ, Một trong những câu hỏi là họ đưa ra một biểu đồ vô hướng G với N nút và M cạnh, Anh ta đưa ra truy vấn Q, trong đó mỗi truy vấn, anh ta đưa ra XYW, ở đâu chúng ta phải kiểm tra xem có một đường đi từ X đến Y với mọi cạnh nhiều nhất phải chứa trọng số <= W. Vì vậy, tôi đã thử lưu trữ các cạnh trong biểu diễn danh sách kề của đồ thị và sử dụng phương pháp DFS và mảng đã thăm để kiểm tra xem có là đường dẫn sau các ràng buộc nhất định. Nó giải quyết cho các trường hợp thử nghiệm một phần chứ không phải cho trường hợp riêng tư. Vì vậy, tôi mặc dù nó có thể là đồ thị dày đặc và tôi đã sử dụng biểu diễn Ma trận của đồ thị, nó đang hiển thị giới hạn bộ nhớ vượt quá. Tôi nên làm gì để giải quyết những loại vấn đề này?

Bất cứ khi nào tôi sử dụng biểu diễn ma trận, nó sẽ vượt quá giới hạn bộ nhớ và nếu tôi sử dụng biểu diễn danh sách gần kề, nó sẽ vượt quá giới hạn thời gian. Hình ảnh câu hỏi

Nhân tiện, kỳ thi đã hoàn thành vài ngày trở lại đây.

Đây là câu hỏi đầu tiên của tôi. Nếu tôi có sai sót gì vui lòng comment bên dưới

Answer 1

Điều này có thể được giải quyết trong O(n log n + q log q), trong khi giải pháp DFS của bạn là O(m*q)và giải pháp ma trận điều chỉnh là O(n^2)không gian

Để giải quyết nhanh vấn đề này, bạn cần biết cấu trúc dữ liệu DSU (Disjiont Set Union) (còn được gọi là Union Find). Nó hỗ trợ O(log n)Liên minh hiệu quả của một số nút và có thể biết một số nút được kết nối hay không cũng trongO(log n)

1. Sắp xếp tất cả các cạnh đã cho theo trọng lượng, tăng dần
2. sắp xếp tất cả các truy vấn đã cho theo trọng số, tăng dần (cũng lưu chỉ mục truy vấn, vì đầu ra sẽ cần theo thứ tự)
3. Bây giờ xử lý từng truy vấn một, nếu truy vấn yêu cầu đường dẫn có các cạnh, hãy <= wthêm tất cả các cạnh vẫn chưa được thêm vào biểu đồ phù hợp với tiêu chí (sử dụng DSU)
4. Bây giờ truy vấn có thể được trả lời bằng cách kiểm tra xem start endcác nút của truy vấn có được kết nối hay không (sử dụng DSU)

Mã mẫu (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":" ");
    }

}