Untitled

mail@pastecode.io avatar
unknown
java
a month ago
2.0 kB
3
Indexable
Never
import java.util.*;

class Solution {
    private final Map<Integer, List<Integer>> adjList;
    private int maxDist;
    private int farthestNode;

    public Solution(int n) {
        adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        maxDist = 0;
        farthestNode = 0;
    }

    public void addEdge(int v, int w) {
        adjList.get(v).add(w);
        adjList.get(w).add(v);
    }

    private void dfs(int node, boolean[] visited, int dist) {
        visited[node] = true;
        if (dist > maxDist) {
            maxDist = dist;
            farthestNode = node;
        }

        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, dist + 1);
            }
        }
    }

    public int solve(int n, int[] network_from, int[] network_to, int[] frequency) {
        Solution solution = new Solution(n);

        for (int i = 0; i < network_from.length; i++) {
            network_from[i]--;
            network_to[i]--;
        }

        for (int i = 0; i < network_from.length; i++) {
            if (Math.abs(frequency[network_from[i]] - frequency[network_to[i]]) <= 1) {
                solution.addEdge(network_from[i], network_to[i]);
            }
        }

        int overallMaxDist = 0;
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            solution.maxDist = 0;
            solution.dfs(i, visited, 0);
            int farthestNode = solution.farthestNode;
            System.out.println("farthestNode: " + (farthestNode + 1));

            boolean[] visited2 = new boolean[n];
            solution.maxDist = 0;
            solution.dfs(farthestNode, visited2, 0);
            overallMaxDist = Math.max(overallMaxDist, solution.maxDist);
        }

        return overallMaxDist;
    }

}
Leave a Comment