Форум программистов, компьютерный форум, киберфорум
Java для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 12.09.2021
Сообщений: 35

Поиск в глубину

21.09.2022, 22:29. Показов 1489. Ответов 0

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

Формат ввода
В первой строке записаны два целых числа N (1 ≤ N ≤ 103) и M (0 ≤ M ≤ 5 * 105) — количество вершин и ребер в графе. В последующих M строках перечислены ребра — пары чисел, определяющие номера вершин, которые соединяют ребра.

Формат вывода
В первую строку выходного файла выведите число K — количество вершин в компоненте связности. Во вторую строку выведите K целых чисел — вершины компоненты связности, перечисленные в порядке возрастания номеров.

Ввод
4 5
2 2
3 4
2 3
1 3
2 4

Вывод
4
1 2 3 4

Не проходит тесты, что не так?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
class Edge //ребро, класс создан для конструктора
{
    int source, dest;
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
 
class Graph //сам граф, в конструктор принимает ребро и кол-во вершин
{
    List<List<Integer>> adjList = null; //все связи
    Graph(List<Edge> edges, int n)
    {
        adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (Edge edge: edges)
        {
            int source = edge.source;
            int dest = edge.dest;
            adjList.get(source).add(dest);
            adjList.get(dest).add(source);
        }
    }
}
 
class Main
{
    public static void DFS(Graph graph, int v, boolean[] used)
    {
        //текущая вершина использована
        used[v] = true;
 
        System.out.print(v + " ");
 
        //проходимся по всем из списка
        for (int j: graph.adjList.get(v))
        {
            if (!used[j]) {
                DFS(graph, j, used);
            }
        }
    }
 
    public static void main(String[] args)
    {
        //считать значения кол-ва вершин и ребер
        //заполнить список с консоля
        //создать граф + массив пройденных вершин
        //напечатать кол-во вершин
        //вызвать дфс в цикле
 
        Scanner con = new Scanner(System.in);
        int n = con.nextInt(); //verc, n+1 в графе, т к с 1 начинаем
        int m = con.nextInt(); //edges
 
 
        List<Edge> edges = Arrays.asList();
 
        for(int i=0; i<m; i++) {
            int v = con.nextInt();
            int w = con.nextInt();
            Edge _ed = new Edge(v, w);
        }
 
        Graph graph = new Graph(edges, n+1);
        boolean[] used = new boolean[n+1];
 
        //num of verc
        System.out.println(graph.adjList.size()-1);
 
        for (int i = 1; i < n+1; i++)
        {
            if (!used[i])
            {
                DFS(graph, i, used);
 
            }
        }
 
 
    }
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
21.09.2022, 22:29
Ответы с готовыми решениями:

Поиск в глубину
Кто то работал с поиском в глубину на java? Возможно у кого то есть примеры простых программ, скиньте плз? Заранее спасибо..

Поиск в глубину. Поиск кратчайшего пути на взвешенном графе (Алгоритм Дейкстры)
Плз.Нужна помощь в проверке кода. Найти количество путей между двумя вершинами в некотором графе Вот код но он вроде бы не совсем...

[Swi-plolog] Поиск в глубину и поиск в ширину
Предмет: &quot;Интеллектуальные системы и технологии&quot; Задание: Поиск в глубину и поиск в ширину. В каждой из девяти клеток квадрата 3*3...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
21.09.2022, 22:29
Помогаю со студенческими работами здесь

Поиск в глубину, поиск в ширину, дерево
Добрый день. Есть задача с бидонами (есть три бидона : 1ый 14 литров -заполнен молоком, 2ой 9 литров-пуст, 3ий 5 литров - пуст. Нужно путем...

Поиск в глубину и поиск в ширину Prolog
Помогите пожалуйста написать программу на Prolog. Не могу разобраться как это реализовать. Поиск в глубину и поиск в ширину. В каждой из...

Поиск в глубину
Добрый день! Нужно изменить готовую задачу под Поиск в глубину ,помогите пожалуйста) Если кажется что в задаче кажется слишком много...

Поиск в глубину
Подскажите плиз, почему не работает прога. Запускается, но не работает. Походу с файла не читает. Кто знает в чем проблема??? program...

Поиск в глубину
Создать программу для решения задачи построения слова из некоторого множества букв (игра Scrabble) используя алгоритмы поиска в глубину и в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных через динамический список в справочнике
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru