Number of pendant vertices 1#5080

Number of pendant vertices 1 (Çözgüdiň düşündirişi)

For each vertex $i$ , count the number of vertices adjacent to it. If this number equals $1$ , then vertex $i$ is a pendant vertex.

Example

The graphs shown in the examples have the following form:

In the first example, the graph contains two vertices of degree $1$ . Therefore, it has two pendant vertices.

In the second example, there are no vertices of degree $1$ (i.e., no pendant vertices).

Algorithm implementation

Declare an array $m$ , where $m [i]$ is the number of vertices adjacent to vertex $i$ .

#define MAX 1010
int m[MAX];

Read the adjacency matrix of an undirected graph. For each edge $(i, j)$ , increase the value of $m [i]$ by $1$ (the value of $m [j]$ will also be increased by $1$ when the edge $(j, i)$ is processed).

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]++;
}

C++

If $m [i] = 1$ m[i] = 1, then vertex $i$ is connected to exactly one vertex, i.e., it is a pendant vertex. Count the number of such vertices and store the result in the variable $r es$ .

res = 0;
for (i = 0; i < n; i++)
  if (m[i] == 1) res++;

Print the answer.

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