Untitled
unknown
java
a year ago
2.0 kB
6
Indexable
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; } }
Editor is loading...
Leave a Comment