Untitled
unknown
plain_text
a year ago
2.5 kB
4
Indexable
Never
import java.util.*; class Graph { private int V; private List<List<Integer>> adj; public Graph(int v) { V = v; adj = new ArrayList<>(v); for (int i = 0; i < v; ++i) { adj.add(new ArrayList<>()); } } public void addEdge(int v, int w) { adj.get(v).add(w); adj.get(w).add(v); } public void removeEdge(int v, int w) { adj.get(v).remove(Integer.valueOf(w)); adj.get(w).remove(Integer.valueOf(v)); } public int countConnectedComponents() { boolean[] visited = new boolean[V]; int count = 0; for (int i = 0; i < V; ++i) { if (!visited[i]) { BFS(i, visited); ++count; } } return count; } private void BFS(int start, boolean[] visited) { Queue<Integer> queue = new LinkedList<>(); queue.add(start); visited[start] = true; while (!queue.isEmpty()) { int vertex = queue.poll(); for (Integer neighbor : adj.get(vertex)) { if (!visited[neighbor]) { queue.add(neighbor); visited[neighbor] = true; } } } } } public class FifthTask { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); Graph graph = new Graph(n); int x, y, d; List<List<Integer>> listOfLists = new ArrayList<>(); for (int i = 0; i < m; i++) { x = scanner.nextInt(); y = scanner.nextInt(); d = scanner.nextInt(); graph.addEdge(x - 1, y - 1); listOfLists.add(new ArrayList<>(List.of(x - 1, y - 1, d))); } listOfLists.sort(Comparator.comparing(list -> list.get(2))); int k = graph.countConnectedComponents(); int t; System.out.println("Количество компонент связности: " + k); for (List<Integer> list : listOfLists) { graph.removeEdge(list.get(0), list.get(1)); t = graph.countConnectedComponents(); if (t != k) { System.out.println(list.get(2) - 1); break; } } } }