我们有n个顶点(其中n小于100 000(和m条随机边(其中m小于10 000 000(。我们想在 2 个给定顶点之间找到一条路径。如果没有路径，我们将只打印 -1。 我的算法是构建一棵树。每个顶点都有一个disjoint_index (i(，它表示所有带有 disjoint_index (i( 的顶点都已连接。
默认值 disjoint_index 是每个顶点的索引。在顶点 v 和你之间找到一条边后，我检查它们是否连接。如果它们有联系，我什么都不做。否则，我会更改您的disjoint_index以及通过名为 (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);
}
}
在这里你可以跳过 kiss，它只是一个返回两个顶点并显示 u 和 v 之间存在边缘的函数。
disjoint_counter[i] 显示连接的组 i 中有多少个顶点。
构建完这棵树后，我会找到一条带有简单 dfs 的路径。时间限制是 1 秒，我在某些测试用例上超过了时间限制。
编辑：内存有限，所以我无法保存所有边缘。 我可以使用的最大内存是 32MB。
我使用了不相交集合并集算法，它开发了速度。