Menemukan jalur pada graf yang tepinya acak

Kita mempunyai n simpul (di mana n kurang dari 100.000) dan m tepi acak (di mana m kurang dari 10.000.000). Kami ingin mencari jalur antara 2 simpul tertentu. Jika tidak ada jalur kami hanya akan mencetak -1. Algoritma saya adalah membangun pohon. Setiap simpul memiliki disjoint_index (i) yang menunjukkan bahwa semua simpul dengan disjoint_index (i), terhubung.

Nilai default disjoint_index adalah indeks setiap titik. Setelah menemukan tepi antara titik v dan u, saya periksa apakah keduanya terhubung. Jika mereka terhubung, saya tidak melakukan apa pun. Kalau tidak, saya mengubah disjoint_index dari u dan semua simpul yang terhubung ke u dengan fungsi bernama (dfs).

Berikut adalah kode fungsi untuk membangun pohon ini di 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);
    }
}

Di sini Anda dapat melewati ciuman, Ini hanya fungsi yang mengembalikan dua simpul dan menunjukkan bahwa ada tepi antara u dan v.

disjoint_counter[i] menunjukkan berapa banyak simpul yang ada di grup terhubung i.

Setelah membangun pohon ini saya akan menemukan jalan dengan dfs sederhana. Batas waktunya adalah 1 detik dan saya mendapatkan Batas Waktu Terlampaui pada beberapa kasus pengujian.

Sunting: Memori terbatas jadi saya tidak bisa menyimpan semua tepinya. Memori maksimum yang dapat saya gunakan adalah 32MB.