Условие:
Имя входного файла: «input.txt»
Имя выходного файла: стандартный поток вывода
Ограничение по времени: 1 second
Ограничение по памяти: 122.17 мегабайт
Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).
Входные данные:
В первой строке содержится количество вершин графа [latex] n [/latex] и выделенная вершина [latex] s [/latex] [latex](1 ≤ s ≤ n ≤ 100) [/latex]. В следующих [latex] n [/latex] строках записано по [latex] n [/latex] чисел — матрица смежности графа, в которой цифра [latex] «0» [/latex] означает отсутствие ребра между вершинами, а цифра [latex] «1» [/latex] — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.
Выходные данные:
Выведите искомое количество вершин.
Тесты:
№ | Входные данные | Выходные данные |
1 |
5 1
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0
|
3 |
2 |
1 1
0
|
1 |
3 |
3 3
0 1 1
1 0 1
1 1 0
|
3 |
4 |
3 1
0 0 0
0 0 1
1 1 0
|
1 |
Решение:
Поскольку нам необходимо найти компоненту связности, запустим из исходной вершины поиск в глубину, запоминая посещенные вершины в массиве [latex] used [/latex]. Те вершины, которые мы посетили — принадлежат той же компоненте связности, что и исходная вершина. Таким образом, подсчитав кол-во посещенных вершин, мы решим задачу.
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 |
package; import cpp.Lib; import sys.io.*; class Main { static function main() { var inp = File.read("input.txt", false); var d = inp.readLine(); var dd = d.split(' '); var n = Std.parseInt(dd[0]); var s = Std.parseInt(dd[1]); s--; var graph = new Array<Array>(); var used = new Array (); function DFS(v : Int){ if (used[v]) return; used[v] = true; for (i in 0...(graph[v].length)){ DFS (graph[v][i]); } } for (i in 0...n){ graph[i] = new Array(); used[i] = false; } for (i in 0...n){ var arr = inp.readLine().split(' '); for (j in 0...n){ if (arr[j] == "1") graph[i].push(j); } } DFS(s); var count = 0; for (i in 0...n){ if (used[i]) count ++; } Sys.stdout().writeString(count + ""); } } |
Маша Лукьянова недавно публиковал (посмотреть все)
- e-olymp 4853. Кратчайший путь - 14.06.2017
- Алгоритм шифрования MARS - 06.05.2017
- e-olymp 4000. Обход в глубину - 24.04.2017
Я пока оставила без рубрики. Думаю, что стоит добавить рубрику графы.