| 1 Нагашыбай Бекарыс Куанышулы, 25 марта 2026 г. 14:07:46 |
| #include <bits/stdc++.h> using namespace std; int n,s,cnt=0,a[101][101],ans=0; bool l[101]; void dfs(int v){ l[v]=1; ans++; for(int i=1;i<=n;i++){ if(l[i]==0&&a[v][i]==1){ dfs(i); } } } int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; if(a[i][j]==1)cnt++; } } if(cnt/2!=n-1){ cout<<"NO"; return 0; } dfs(1); if(ans==n){ cout<<"YES"; return 0; } cout<<"NO"; }
|
|
|
| 2 Неизвестный, 18 ноября 2025 г. 15:50:43 |
| Я решил задачу c BFS
|
|
|
| 3 Неизвестный, 18 ноября 2025 г. 15:50:26 |
| Граф называется деревом если все вершины связны/смежны,и у него n-1 ребро.Если такое условие не соблюдаються значить граф не дерево
|
|
|
| 4 Вашурин Анатолий Александрович, 16 августа 2025 г. 10:56:18 |
| Лапкин Григорий, в графе может быть цикл
|
|
|
| 5 Лапкин Григорий, 06 февраля 2025 г. 13:42:50 |
| Уважаемы коллеги, не проходит 11 тест. Мой код не использует ни оход в глубину, ни в ширину. Все что он делает, это считает сумму единичек в каждой строке и делит ее на два, получая количество вершин. Если сумма хотя бы одной вершины равна 0, то сразу выдает ошибку, т к нарушается условие связности Не могу понять, в чем ошибка Подскажите, пожалуйста
|
|
|
| 6 Серикбек Асанали, 29 ноября 2022 г. 6:52:15 |
| Проверка ребра = вершины - 1 не достаточна, так как может быть такое, что в графе будут циклы, несколько компонентов связности. В дереве циклов нет
|
|
|
| 7 Кунг Фу Падла, 24 октября 2022 г. 17:24:44 |
| ребят, почему не достаточно проверить что колво ребер = колво вершин - 1?
|
|
|
| 8 Махмадиеров Фахриддин, 25 ноября 2020 г. 0:47:12 |
| Можно решать с bfsом и dfsом
|
|
|
| 9 Уткир, 24 августа 2019 г. 18:35:53 |
| 3 0 1 1 1 0 1 0 1 0 YES это правда
|
|
|
| 10 Тимчук Денис Віталійович, 10 июня 2017 г. 13:31:41 |
| Задача очень хорошая, с помощю нее освоил dfs благадорю
|
|
|
| 11 Юсупов Темиржан Нурланович, 16 апреля 2016 г. 18:15:44 |
В этом тесте тоже "NO", помните, что дерево - ациклический граф, то есть между всеми парами вершин есть только один путь. Количество ребер = количество вершин - 1.
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
|
|
|
| 12 Гимадутдинов Рустем, 28 июля 2015 г. 17:09:52 |
Идея такая:
1) Проверяем граф на связность ДФС'ом и находим кол-во ребер.
2) Если граф связный и кол-во ребер равно n - 1, то выводим YES, иначе NO.
|
|
|
| 13 Суворов Виктор, 02 марта 2015 г. 21:10:01 |
| Пределы входных данных так малы, что можно не париться и проверять связность матрицей достижимости, построенной алгоритмом Флойда-Уоршелла.
|
|
|
| 14 Снытко Максим Александрович, 05 февраля 2012 г. 15:05:06 |
| Дерево — это связный ациклический граф (то есть граф, не содержащий циклов, между любой парой вершин которого существует ровно один путь)
|
|
|
| 15 Орынбаев Хусаин Рамазанович, 05 февраля 2011 г. 21:37:22 |
скорее всего я не донял что означает граф дерево, эх старушка википедия я к тебе в гости
|
|
|
| 16 Modiv, 13 мая 2010 г. 18:58:07 |
А первый тест совпадает с первым тестом в примере?
совпадает
|
|
|
| 17 Abzal Serekov, 26 июля 2008 г. 15:20:20 |
Посоветуйте, в какой книге есть все об графах?
А задачи на графы часто приходят в олимпиадах, примерно какие?
Надеюсь, что когда-нибудь у меня на этом сайте появится теория по графам. Скажу, что задачи на графы бывают очень часто на олимпиадах, практически всегда.
|
|
|
