import org.openjdk.jmh.annotations.*;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.TimeUnit;

@State(Scope.Benchmark)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Graph {
    private int[][] g;
    private static final int SIZE = 1000;

    @Setup
    public void setup() {
        Random r = new Random();
        g = new int[SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (i == j) continue;
                if (r.nextBoolean()) {
                    g[i][j] = g[j][i] = 1;
                }
            }
        }

    }

    private class DfsRunner {
        boolean[] visited;

        public DfsRunner() {
            visited = new boolean[SIZE];
        }

        public void run(int v) {
            visited[v] = true;
            for (int u = 0; u < SIZE; u++) {
                if (g[v][u] == 1 && !visited[u]) {
                    run(u);
                }
            }
        }
    }

    @GenerateMicroBenchmark
    public boolean dfs() {
        DfsRunner dfsRunner = new DfsRunner();
        dfsRunner.run(0);
        for (int i = 0; i < SIZE; i++) {
            if (!dfsRunner.visited[i]) return false;
        }
        return true;
    }

    @GenerateMicroBenchmark
    public boolean bfs() {
        boolean[] visited = new boolean[SIZE];

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            visited[v] = true;
            for (int u = 0; u < SIZE; u++) {
                if (g[v][u] == 1 && !visited[u]) {
                    visited[u] = true;
                    queue.add(u);
                }
            }
        }

        for (int i = 0; i < SIZE; i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
}