Обнаружение цикла в Графике с использованием find и Union

Проблема с вашим вход, но сначала немного предыстории:

Предыстория использования Union-Find для обнаружения циклов

Алгоритм Union-Find ожидает неориентированный граф.

По сути, это работает следующим образом:

• Создайте набор ребер, которые в основном являются парами идентификаторов узлов
  • например (1,2), (2,3)
• Для каждого края:
  • найти «родителя» левой стороны (найти Порция)
  • найти «родителя» правой стороны (найти Порция)
  • если родители идентичны, у вас есть цикл
  • в противном случае родитель левой стороны теперь равен родителю правой стороны (союз Порция)

«Родитель»: произвольное обозначение между двумя ненаправленными узлами. Произвольно мы говорим, что один является родителем другого, а не наоборот.

• Во-первых, ни у одного узла нет родителя (значение которого в -1 используется для.
• Затем, перебирая ребра, вы назначаете этих родителей
  • если родитель не существует, узел является его собственным родителем (0 — родитель 0, 1 — родитель 1 и т. д.)
  • после вычисления родителей для обеих сторон ребра (например, 1 а также 2 для края (1, 2) Сначала мы увидим, что их родители не одинаковы (родитель 1 — 1, а родитель 2 — 2).
  • На данный момент мы союз родители, чтобы сделать их одинаковыми
    • родитель 1 становится 2, а родитель 2 остается 2
    • часть «Объединение» следует рассматривать как «объединение двух подмножеств узлов под общим родителем», поэтому подмножества 1 и 2 становятся (1, 2), чьим родителем является 2.

Однако, как ваш алгоритм написан, это предполагает что если мы впервые получим преимущество (1, 2)тогда мы будем не позже получить преимущество (2, 1), Ваш вклад не согласен. Поэтому у вас есть циклы.

Если вы удалите эти избыточные ребра и предоставите ввод, как:

1 2 3
2 4 5
3
4
5

Это будет работать(У меня C ++ — кстати, черт побери из твоего кода). Однако в противном случае он будет правильно сообщать о цикле

Ваш вызов

Поэтому стоит принять во внимание, что ваш ввод отличается от того, что ожидает ваш алгоритм. То есть, вы, вероятно, не должны создавать ребра, если они уже существуют.

Что я бы порекомендовал:
— поскольку график не ориентирован, сохраняйте ребра с меньшим идентификатором всегда слева. Вы можете сохранить отсортированный список ребер и не вставлять повторяющиеся ребра (используйте std::set), чтобы представить свой крайний список).

Полученный код выглядит примерно так (используя cin для ввода):

using edge_t = std::pair<int, int>;
using edge_list_t = std::set<edge_t>;
using parent_child_map_t = std::map<int, int>;

// find the parent for an id
int find(const parent_child_map_t& idToParent, int id)
{
auto iter = idToParent.find(id);
if (iter == idToParent.end())
return id;
return find(idToParent, iter->second);
}

// lhsId and rhsId are two sides to an edge
// this Union function will determine who is the "parent"// arbitrarily choosing the rhsId's parent as lhsId's parent
void ComputeUnion(parent_child_map_t* idToParent, int lhsId, int rhsId)
{
if (!idToParent)
return;

int xsubset = find(*idToParent, lhsId);
int ysubset = find(*idToParent, rhsId);
(*idToParent)[xsubset] = ysubset;
}

bool HasCycle(const edge_list_t& edges )
{
// determine parents
parent_child_map_t idToParent;

for (auto&& nextEdge : edges)
{
int x = find(idToParent, nextEdge.first);
int y = find(idToParent, nextEdge.second);
if (x == y)
return true;
ComputeUnion(&idToParent, x, y);
}

return false;
}

int main()
{
edge_list_t edges;

std::string nextline;
while(std::getline(std::cin, nextline))
{
std::istringstream nextLineStream(nextline);
int id;
nextLineStream >> id;
int nextNeighbor;
while(nextLineStream >> nextNeighbor)
{
int lhs = std::min(id, nextNeighbor);
int rhs = std::max(id, nextNeighbor);
edges.insert(std::make_pair(lhs, rhs));
}
}

if (HasCycle(edges))
std::cout << "Graph contains cycle\n";
else
std::cout << "Graph does not contain cycle\n";

return 0;
}

И теперь он больше не сообщает о цикле в вашем входе!

Но, если мы предоставим входные данные следующим образом (обратите внимание на дополнительный край (4,1)):

1 2 3
1 2 3
2 1 4 5
3 1
4 2 1
5 2

Тогда он правильно сообщает цикл!