Составьте программу, выполняющую поиск наибольшей компоненты связности в неориентированном мультиграфе. Наибольшей считается компонента, содержащая максимальное количество вершин. Если две или более компоненты содержат одинаковое количество вершин, то выбирается та из них, в которой больше рёбер. Если же и это не позволяет однозначно выбрать наибольшую компоненту, следует предпочесть компоненту, содержащую минимальную по номеру вершину.
В случае, если языком реализации программы выбран язык Java, то точкой входа в программу должен являться метод main класса MaxComponent.
Программа должна считывать со стандартного потока ввода количество вершин графа N (1≤N≤1000000), количество рёбер M (0≤M≤1000000) и данные о рёбрах графа. При этом каждое ребро кодируется номерами инцидентных ему вершин u и v такими, что 0≤u,v<N−1.
Программа должна формировать в стандартном потоке вывода описание графа в формате DOT. При этом вершины графа должны быть помечены своими номерами, и, кроме того, вершины и рёбра наибольшей компоненты должны быть раскрашены красным цветом.
Карта представляет собой целочисленную матрицу размера N×N.
Путь на карте – это последовательность элементов карты с координатами (x1,y1),(x2,y2),…,(xk,yk) такая, что для любых двух соседних элементов последовательности справедливо одно утверждение из двух:
x-координаты элементов совпадают, а y-координаты различаются на единицу; y-координаты элементов совпадают, а x-координаты различаются на единицу. Длина пути – это сумма его элементов.
Например, пусть дана карта:
- 2 1 3
- 5 8 2
- 7 1 6
Тогда (1,1),(1,2),(1,3),(2,3),(3,3) – путь, имеющий длину 14.
Требуется составить программу, вычисляющую минимальную длину пути, соединяющего точки (1,1) и (N,N). В случае, если языком реализации программы выбран язык Java, то точкой входа в программу должен являться метод main класса MapRoute.
Программа должна считывать из входного потока размер N карты (1≤N≤1500) и саму карту. Карта содержит целые числа от 0 до 9.
Программа должна выводить в выходной поток целое число – минимальную длину пути.