Untitled

mail@pastecode.io avatar
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;
            }
        }
    }

}