У нас есть n вершин (где n меньше 100 000) и m случайных ребер (где m меньше 10 000 000). Мы хотим найти путь между двумя заданными вершинами. Если пути нет, мы просто напечатаем -1. Мой алгоритм состоит в том, чтобы построить дерево. Каждая вершина имеет индекс disjoint_index (i), который показывает, что все вершины с индексом disjoint_index (i) связаны.
Значение по умолчанию disjoint_index — это индекс каждой вершины. Найдя ребро между вершинами v и u, я проверяю, соединены ли они. Если они подключены, я ничего не делаю. В противном случае я изменяю disjoint_index u и всех вершин, связанных с u, с помощью функции с именем (dfs).
Вот код функции для построения этого дерева на С++:
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 с, и я получаю превышение лимита времени в некоторых тестовых случаях.
Изменить: память ограничена, поэтому я не могу сохранить все края. Максимальный объем памяти, который я могу использовать, составляет 32 МБ.
