fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int gr[1001][1001]; // матрица смежности
  6. int n; //кол-во вершин
  7.  
  8. //Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
  9. //инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
  10. //Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице
  11. //только одна единица, то вершина имеет степень 1 и является висячей.
  12.  
  13. int main() {
  14. ios::sync_with_stdio(false);
  15. cin >> n;
  16. int ans = 0; //предположим, что граф не имеет висячих вершин
  17. for (int i=0; i<n; i++)
  18. for (int j=0; j<n; j++)
  19. cin >> gr[i][j]; //ввод матрицы смежности
  20. for (int i=0; i<n; i++){
  21. int cnt = 0; //счётчик
  22. for (int j=0; j<n; j++){
  23. if (gr[i][j] == 1) cnt++; //подсчёт степени
  24. }
  25. if (cnt==1) ans++; //проверка на висячую вершину
  26. }
  27. cout << ans << endl; //вывод ответа
  28. return 0;
  29. }
Success #stdin #stdout 0s 7144KB
stdin
3
1 0 1
1 0 0
0 0 1
stdout
2