Код:
|
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 |
#include <iostream> #include <vector> using namespace std; int gr[1001][1001]; // матрица смежности int n; //кол-во вершин //Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во //инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине. //Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице //только одна единица, то вершина имеет степень 1 и является висячей. int main() { ios::sync_with_stdio(false); cin >> n; int ans = 0; //предположим, что граф не имеет висячих вершин for (int i=0; i<n; i++) for (int j=0; j<n; j++) cin >> gr[i][j]; //ввод матрицы смежности for (int i=0; i<n; i++){ int cnt = 0; //счётчик for (int j=0; j<n; j++){ if (gr[i][j] == 1) cnt++; //подсчёт степени } if (cnt==1) ans++; //проверка на висячую вершину } cout << ans << endl; //вывод ответа return 0; } |
Пожалуйста, на основании комментариев сделайте описание алгоритма. Хоть оно и простое, но нужно сделать.