Алгоритм Флойда поиска цикла

Question

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

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

Answer 1

Вот код на с++ с использованием алгоритма Флойда, который находит цикл в невзвешенном ориентированном графе с 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 иначе

БЛОГ НА HUSL

Алгоритм Флойда поиска цикла

Ответы (1 шт):