Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной (считая эту вершину).
В первой строке входных данных содержатся два числа: \(N\) и \(S\) \((1 \leq N \leq 100; 1 \leq S \leq N)\), где \(N\) – количество вершин графа, а \(S\) – заданная вершина. В следующих \(N\) строках записано по \(N\) чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.
Выведите одно целое число – искомое количество вершин.
| Ввод | Вывод |
|---|---|
3 1 0 1 1 1 0 0 1 0 0 |
3 |
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их.
Во входном файле записано два числа \(N\) и \(M\) \((0 \lt N \leq 100000, 0 \leq M \leq 100000)\). В следующих \(M\) строках записаны по два числа \(i\) и \(j\) \((1 \leq i, j \leq N)\), которые означают, что вершины \(i\) и \(j\) соединены ребром.
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.
| Ввод | Вывод |
|---|---|
6 4 3 1 1 2 5 4 2 3 |
3 3 1 2 3 2 4 5 1 6 |
Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
В первой строке входного файла содержится одно натуральное число \(N\) \((N \leq 100)\) - количество вершин в графе. Далее в \(N\) строках по \(N\) чисел - матрица смежности графа: в \(i\)-ой строке на \(j\)-ом месте стоит 1, если вершины \(i\) и \(j\) соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Вывести "YES", если граф является деревом, и "NO" иначе.
| Ввод | Вывод |
|---|---|
6 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 |
NO |
3 0 1 0 1 0 1 0 1 0 |
YES |
Дан ориентированный граф. Требуется определить, есть ли в нем цикл.
В первой строке вводится число вершин \(N \leq 50\). Далее в \(N\) строках следуют по \(N\) чисел, каждое из которых – 0 или 1. \(j\)-ое число в \(i\)-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из \(i\)-ой вершины в \(j\)-ую. Гарантируется, что на диагонали матрицы будут стоять нули.
Выведите 0, если в заданном графе цикла нет, и 1, если он есть.
| Ввод | Вывод |
|---|---|
3 0 1 0 0 0 1 0 0 0 |
0 |
3 0 1 0 0 0 1 1 0 0 |
1 |
Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его.
В первой строке дано одно число \(n\) — количество вершин в графе \((1 \leq n \leq 500 )\). Далее в \(n\) строках задан сам граф матрицей смежности.
Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число \(k\) — количество вершин в цикле, а в третьей строке выведите \(k\) различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.
| Ввод | Вывод |
|---|---|
3 0 1 1 1 0 1 1 1 0 |
YES 3 3 2 1 |
4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 |
NO |
Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.
У профессора записаны все пары студентов, обменявшихся записками. Требуется определить, сможет ли он разделить студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы.
В первой строке находятся два числа \(N\) и \(M\) - количество студентов и количество пар студентов, обменивающихся записками \((1 \leq N \leq 100, 0 \leq M \leq \frac{N \cdot (N−1)}{2})\). Далее в \(M\) строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.
Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.
| Ввод | Вывод |
|---|---|
3 2 1 2 2 3 |
YES |
3 3 1 2 2 3 1 3 |
NO |
Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.
Сначала вводятся два числа: \(N\) (от 1 до 100) и \(M\) – количество вершин и ребер графа соответственно. Далее идет \(M\) пар чисел, задающих ребра. Гарантируется, что граф связный.
Выведите \(N - 1\) пару чисел – ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.
| Ввод | Вывод |
|---|---|
4 4 1 2 2 3 3 4 4 1 |
1 2 2 3 3 4 |
Диаметром дерева называется максимальное из всех расстояний между парой его вершин.
Дано дерево, содержащее \(N\) вершин. Требуется вычислить его диаметр.
Первая строка содержит натуральное число \(N\) \((1 \leq N \leq 2 \cdot 10^5)\).
В следующих \(N − 1\) строках записаны рёбра дерева. В каждой строке записана пара чисел a и b, разделённых пробелом \((1 \leq a,b \leq N)\) — ребро между вершинами a и b.
Программа должна вывести одно число — диаметр дерева.
| Ввод | Вывод |
|---|---|
5 1 2 1 3 3 4 3 5 |
3 |