5080. Количество висячих вершин 1

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна 1.

Вход. В первой строке находится число n (1 ≤ n ≤ 1000). В следующих n строках находится матрица смежности.

Выход. Выведите количество висячих вершин в графе.

Пример входа 1	Пример выхода 1
2 0 1 1 0	2
Пример входа 2	Пример выхода 2
3 0 1 1 1 0 1 1 1 0	0

РЕШЕНИЕ

графы

Анализ алгоритма

Для каждой вершины i подсчитаем количество вершин, смежных с ней. Если это число равно 1, то i висячая.

Пример

Графы, приведенные в примерах, имеют вид:

В первом примере граф содержит две вершины со степенью 1. Следовательно две вершины в нем висячие.

Во втором примере вершин со степенью 1 (висячих) нет.

Реализация алгоритма

Объявим массив m. В m[i] будем подсчитывать количество вершин, смежных с i.

#define MAX 1010

int m[MAX];

Читаем матрицу смежности неориентированного графа. Для каждого ребра (i, j) увеличим на 1 значение m[i] (m[j] на 1 увеличится соответственно когда будет рассматриваться ребро (j, i) ).

scanf("%d",&n);

memset(m,0,sizeof(m));

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

{

scanf("%d",&val);

if (val) m[i]++;

}

Если m[i] = 1, то с вершиной i связана только одна вершина, то есть i является висячей. Подсчитываем количество висячих вершин в переменной res.

for(res = i = 0; i < n; i++)

if (m[i] == 1) res++;

printf("%d\n",res);

Java реализация

import java.util.*;

//import java.io.*;

public class Main

{

public static void main(String[] args) // throws IOException

{

//Scanner con = new Scanner(new FileReader ("5080.in"));

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

{

int val = con.nextInt();

if (val == 1) m[i]++;

}

int res = 0;

for(int i = 0; i < n; i++)

if (m[i] == 1) res++;

System.out.println(res);

con.close();

}

}