时间戳

首页 > 解决方案 > 在具有随机边的图中查找路径

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

问题描述

我们有 n 个顶点（其中 n 小于 100 000）和 m 个随机边（其中 m 小于 10 000 000）。我们想找到两个给定顶点之间的路径。如果没有路径，我们将只打印 -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，它只是一个返回两个顶点并显示u和v之间有一条边的函数。

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

在构建这棵树之后，我会找到一条带有简单 dfs 的路径。时间限制是 1 秒，我在某些测试用例中得到了 Time Limit Exceeded。

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

标签： c++graphtreedepth-first-search

解决方案

我使用了不相交集联合算法，它提高了速度。

推荐阅读