0

Здравствуйте при написании алгоритма Флойда для поиска цикла. Столкнулся с проблемой, не проходят все тесты. Код алгоритма:

static class   Node {
        String data;
        Node next;
        Node(String d){
            data = d;
            next = null;
        }
    }


public void push(String newData) {
        Node newNode = new Node(newData);

        newNode.next = head;
        head = newNode;
    }

public boolean detectLoop() {
        Node slow = head;
        Node fast = head;
        int flag = 0;

        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) {
                flag = 1;
                break;
            }
        }

        return flag != 1;

    }

Вызов метода и парсинг данных

LinkedList<String> d = new LinkedList<>();

        for (String[] x : libraries.dependencies) {
            Collections.addAll(d, x);
        }

        FloydsCycleFinding floydsCycleFinding = new FloydsCycleFinding();
        for (String x : d) {
            floydsCycleFinding.push(x);
        }

        return floydsCycleFinding.detectLoop();

Тесты которые не проходят, у меня только подсказки:

Первый тест:

Input:"AA", "AB", "AB", "AA"
Text: "Should fail with direct internal dependency"
Expected :false
Actual   :true

Второй тест:

Input: "AA", "AB", "AB", "AC", "AC", "AB"
Text: Should fail with inderect dependencies
Expected :false
Actual   :true
13
  • Где код парсинга входных параметров и построения графа? 6 мая 2021 в 18:14
  • @AntonShchyrov добавил
    – kiker
    6 мая 2021 в 18:16
  • @AntonShchyrov я исчу в LinkedList, так как не смог разобратся как сделать поиск цылка в графе Strig`ов
    – kiker
    6 мая 2021 в 18:19
  • 1
    Так вы же в методе push сами зацикливаете граф. И почему у вас в ноде только одно поле next? Разве у вершины не может быть более одного соседа? 6 мая 2021 в 18:21
  • 1
    Флойд много чего придумал. В вашем коде использован алгоритм Флойда (заяц-черепаха) поиска петли (цикла) в односвязном списке, а, судя по задаче, у вас граф обшего вида. В ответе алгоритм Флойда-Уоршелла. Но именно для поиска цикла это не лучший выбор - достаточно поиска в глубину.
    – MBo
    7 мая 2021 в 13:02

1 ответ 1

3

Вот код на с++ с использованием алгоритма Флойда, который находит цикл в невзвешенном ориентированном графе с n вершинами, который задается матрицей смежности.

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <vector<long long>> dp(n, vector <long long> (n, INF));
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            cin >> dp[i][j];
            if (dp[i][j] == 0 && i != j){
                dp[i][j] = INF;
            }
            else {
                dp[i][j] *= -1;
            }
        }
    }
    for (int k = 0; k < n; ++k){
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                if (dp[i][k] != INF && dp[k][j] != INF) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    for (int k = 0; k < n; ++k){
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                if (dp[i][k] != INF && dp[k][j] != INF && dp[k][k] < 0) {
                    dp[i][j] = -INF;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            if (dp[i][j] == -INF){
                cout << 1;
                return 0;
            }
        }
    }
    cout << 0;
    return 0;
}

Выводит 1, если цикл есть, и 0 иначе

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.