eanea / graph

Graph

Наибольший компонент

Составьте программу, выполняющую поиск наибольшей компоненты связности в неориентированном мультиграфе. Наибольшей считается компонента, содержащая максимальное количество вершин. Если две или более компоненты содержат одинаковое количество вершин, то выбирается та из них, в которой больше рёбер. Если же и это не позволяет однозначно выбрать наибольшую компоненту, следует предпочесть компоненту, содержащую минимальную по номеру вершину.

В случае, если языком реализации программы выбран язык 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.

Программа должна выводить в выходной поток целое число – минимальную длину пути.