การค้นหาเส้นทางในกราฟด้วยการสุ่มขอบ

เรามีจุดยอด n จุด (โดยที่ n น้อยกว่า 100,000) และขอบสุ่ม m (โดยที่ m น้อยกว่า 10,000,000) เราต้องการค้นหาเส้นทางระหว่างจุดยอดที่กำหนด 2 จุด หากไม่มีเส้นทางเราจะพิมพ์ -1 อัลกอริทึมของฉันคือการสร้างต้นไม้ จุดยอดทุกจุดจะมี disjoint_index (i) ซึ่งแสดงว่าจุดยอดทั้งหมดที่มี disjoint_index (i) เชื่อมต่อกัน

ค่าเริ่มต้นของ disjoint_index คือดัชนีของแต่ละจุดยอด หลังจากหาขอบระหว่างจุดยอด v และ u แล้ว ฉันจะตรวจสอบว่ามันเชื่อมต่อกันหรือไม่ หากพวกเขาเชื่อมต่อกัน ฉันจะไม่ทำอะไรเลย มิฉะนั้น ฉันจะเปลี่ยน disjoint_index ของ u และจุดยอดทั้งหมดที่เชื่อมต่อกับ u ด้วยฟังก์ชันชื่อ (dfs)

นี่คือโค้ดของฟังก์ชันในการสร้างแผนผังนี้ใน c++:

struct vertex{
    int disjoint_index;
    vector<int> adjacent;
};

void build_tree(int m, int s, int e)
{
    for(int i = 0; i < m; i++)
    {
        int u = kiss() % n;
        int v = kiss() % n;

        if(disjoint_counter[u] > disjoint_counter[v])
        {
            int temp = u;
            u = v;
            v = temp;
        }//counter v > u

        if(ver[v].disjoint_index != ver[u].disjoint_index)
        {
            ver[v].adjacent.push_back(u);
            ver[u].adjacent.push_back(v);

            dfs(v, u, ver[v].disjoint_index);

            disjoint_counter[v] += disjoint_counter[u];
        }

        if(ver[s].disjoint_index == ver[e].disjoint_index)
            return;
    }
}

void dfs(int parent, int v, int d)
{
    ver[v].disjoint_index = d;
    for(int i = 0; i < ver[v].adjacent.size(); i++)
    {
        if(ver[v].adjacent[i] == parent)
            continue;
        dfs(v, ver[v].adjacent[i], d);
    }
}

ที่นี่คุณสามารถข้ามการจูบได้ มันเป็นเพียงฟังก์ชันที่ส่งคืนจุดยอดสองจุดและแสดงว่ามีขอบระหว่าง u และ v

disjoint_counter[i] แสดงจำนวนจุดยอดที่อยู่ในกลุ่มที่เชื่อมต่อ i

หลังจากสร้างแผนผังนี้แล้ว ฉันจะพบเส้นทางที่มี dfs ที่เรียบง่าย การจำกัดเวลาคือ 1 วินาที และฉันได้รับ Time Limit Exceeded ในกรณีทดสอบบางกรณี

แก้ไข: หน่วยความจำมีจำกัด ดังนั้นฉันจึงไม่สามารถบันทึกขอบทั้งหมดได้ หน่วยความจำสูงสุดที่ฉันสามารถใช้ได้คือ 32MB