在具有随机边的图中查找路径

Question

我们有 n 个顶点（其中 n 小于 100 000）和 m 个随机边（其中 m 小于 10 000 000）。我们想找到 2 个给定顶点之间的路径。如果没有路径，我们将只打印 -1。我的算法是构建一棵树。每个顶点都有一个 disjoint_index (i) 这表明所有具有 disjoint_index (i) 的顶点都已连接。

默认值disjoint_index是每个顶点的索引。找到顶点 v 和 u 之间的边后，我检查它们是否相连。如果它们已连接，我什么都不做。否则我通过名为 (dfs) 的函数更改 u 的 disjoint_index 和所有连接到 u 的顶点。

这是用 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);
    }
}

这里可以跳过kiss，它只是一个returns两个顶点的函数，表示u和v之间有一条边

disjoint_counter[i] 显示连接组 i 中有多少个顶点。

构建这棵树后，我将找到一条带有简单 dfs 的路径。时间限制是 1 秒，我在某些测试用例上超出了时间限制。

编辑：内存有限，所以我无法保存所有边。我可以使用的最大内存是 32MB。

Answer 1

我用的是disjoint set union算法，开发速度很快

在具有随机边的图中查找路径

Finding a path in a graph with random edges

c++

tree

graph

depth-first-search