java是在大型有向图中查找所有循环的最快方法

Question

我必须在一个有向图中找到所有的循环，其中每个节点只需要到一个节点，但它可以有多个节点到它，并打印一个循环中的所有节点

有什么方法可以让[我的代码][1]运行得更快吗

目前，它以大约4s的速度运行100k个节点，但时间限制为1.5s

import java.io.*;
import java.util.*;

public class Main {
    public static void main (String[] args) throws IOException {
        long startTime = 0;
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        int numOfPeople = Integer.parseInt(input.readLine());
        StringTokenizer following = new StringTokenizer(input.readLine(), " ");
        startTime = System.nanoTime();

        int[] people = new int[numOfPeople],               // index -> personID, value -> personID's friend
                winningPotentials = new int[numOfPeople];  // index -> personID, value -> personID's winningPotential
        Arrays.fill(winningPotentials, 50);

        // adding followings of people
        for (int i = 0 ; i < numOfPeople ; i++) {
            people[i] = Integer.parseInt(following.nextToken()) - 1;
        }

        /*
                SETTING WINNER POTENTIALS
         */
        int numOfWinners = 0;
        for (int person : people) {
            if (winningPotentials[person] == 50) {
                Deque<Integer> path = new ArrayDeque<>();
                path.addLast(person);

                while (true) {
                    int friend = people[person];

                    if (path.contains(friend)) {
                        // all those in a friend group are winningPot = 100
                        while (path.getLast() != friend) {
                            if (winningPotentials[path.peekLast()] != 100) {
                                numOfWinners++;
                                winningPotentials[path.peekLast()] = 100;
                            }
                            path.removeLast();
                        }
                        if (winningPotentials[path.peekLast()] != 100) {
                            numOfWinners++;
                            winningPotentials[path.peekLast()] = 100;
                        }
                        path.removeLast();

                        break;
                    }
                    // if friend hasn't been checked before, repeat
                    else {
                        path.addLast(friend);
                        person = friend;
                    }
                }
                // anyone in the path that wasnt in a friend group is winnerPot=0
                for (int person2 : path)
                    winningPotentials[person2] = 0;
            }
        }

        /*
                PRINTING THE RESULTS
        */
        StringBuilder sb = new StringBuilder();
        sb.append(numOfWinners + "\n");

        // print each winner
        for (int i = 0 ; i < winningPotentials.length ; i++)
            if (winningPotentials[i] == 100)
                sb.append((i + 1) + " ");
        sb.append("\nExecution Time ->\t" + ((System.nanoTime() - startTime) / 1000000) + "ms");
        output.write(sb.toString());
        output.flush();
        output.close();
    }
}

Answer 1

为什么您需要缓冲写入程序？你能不能不做一个System.out.println(sb.toString())

Answer 2

这可以作为一种改进的BFS算法来实现

不同之处在于，每当您看到一个已经添加到队列中的点，而不是您刚才所在的点之前的点时，您就发现了一个循环。因此，在向队列中添加点时，可以将当前路径添加到该点，而不仅仅是该点，还可以将相邻点（路径上的最后一个点）添加到已找到点的列表中

我可能会等到你找到所有的循环后再计算获胜的可能性